1 Logistics & ITS, Department of Transport, Technical University of Denmark2 Department of Transport, Technical University of Denmark3 Operations Research, Department of Management Engineering, Technical University of Denmark4 Department of Management Engineering, Technical University of Denmark
This thesis treats two different planning problems from the transportation industry; one from freight transport and one from passenger transport. Each problem emerges as a combination of problems that are already known from the operational research literature, and introduces a new view of well-known issues. They both originate in the world of multimodality, and deal with problems that arise as a consequence of the combined use of several modes. The thesis introduces the Double Travelling Salesman Problem with Multiple Stacks (DTSPMS), which is a problem that combines routing and last-in-first-out loading constraints. After giving an introduction to the problem, a range of related problems from the literature are discussed. Some considerations are made regarding basic bounds for the problem, and illustrations of problem solutions are given to provide an impression of how solutions of the DTSPMS compare to solutions of the regular Travelling Salesman Problem. Next, two papers are presented, introducing respectively heuristic and exact solution procedures for the problem. The heuristic approach tests a variety of metaheuristic solution approaches, of which a large neighbourhood search obtains the best results. Results are provided for real-life instance sizes, for smaller instances for which the optimal solution value is known, and for some larger instances, which can also be justified from a real-life perspective. With the purpose of solving the DTSPMS to optimality, several different mathematical formulation are presented and tested in the second paper. The most promising approach is based on a decomposition of the problem into a routing part and a loading feasibility part, and all tested instances with 15 orders can be solved using this approach. The Simultaneous Vehicle Scheduling and Passenger Service Problem (SVSPSP) is an integration of two problems that are usually solved separately and sequentially, namely the timetabling problem and the Vehicle Scheduling Problem. The SVSPSP allows for the solution of the timetabling problem to be reoptimised when considering the vehicle scheduling phase, and considers passenger inconvenience at transfers at the same time. The paper presents a mathematical model of the problem, and the implementation of a large neighbourhood search solution procedure. The problem is solved for a real-life based problem instance, containing eight bus lines in the Greater Copenhagen area, and the results are promising.
double travelling salesman with multiple stacks; mathematical modelling; simultaneous vehicle scheduling and passenger service problem; multimodal transportation