1 Logistics & ITS, Department of Transport, Technical University of Denmark2 Department of Management Engineering, Technical University of Denmark3 Operations Research, Department of Management Engineering, Technical University of Denmark
The Vehicle Routing Problem (VRP) is one of the most important and challenging optimization problems in the field of Operations Research. It was introduced by Dantzig and Ramser (1959) and defined as the problem of designing the optimal set of routes for a fleet of vehicles in order to serve a given set of customers. The VRP is a computationally hard combinatorial problem and has been intensively studied by numerous researchers in the last fifty years. Due to the significant economic benefit that can be achieved by optimizing the routing problems in practice, more and more attention has been given to various extensions of the VRP that arise in real life. These extensions are often called Rich Vehicle Routing Problems (RVRPs). In contrast to the research of classical VRP that focuses on the idealized models with unrealistic assumptions, the research of RVRPs considers those complicated constraints encountered in the real-life planning and provides solutions that are executable in practice. In this thesis, we investigated the models and algorithms of three practical vehicle routing problems. Each of them involves special practical issues that are only considered in very few papers. Our study of these problems was motivated by our cooperation with industrial companies, particularly Transvision A/S and its client distributors, and Danish Crown. The models and methods proposed in the thesis are general and can be applied to practical routing problems arising in many other distribution companies as well. We first consider a vehicle routing problem with cross-docking options, in which products are picked up from suppliers by vehicles, consolidated at the depot and immediately delivered to customers by the same set of vehicles. It is more complex than the traditional vehicle routing problems in the sense that consolidation decisions have to be made at the depot and these decisions interact with the planning of pickup and delivery routes. We presented a mathematical model and proposed a Tabu Search based heuristic to solve it. It is shown that the approach can produce near-optimal solutions within very short computational time on real-life data involving up to 200 pairs of suppliers and customers. The second problem we consider is a dynamic vehicle routing problem with multiple objectives over a planning horizon that consists of multiple periods. In this problem, customer orders are revealed incrementally over the planning horizon. The delivery plan must be made and executed in every period without knowing the future orders. We modeled the problem as a mixed integer linear program and solved it by means of a three-phase heuristic that works over a rolling planning horizon. The method improves the company’s solution in terms of all the objectives, including the travel time, customer waiting and daily workload balances, under the given constraints considered in the work. Finally, we address an integrated vehicle routing and driver scheduling problem, in which a large number of practical constraints are considered, such as the multi-period horizon, the time windows for the delivery, the heterogeneous vehicles, the drivers’ predefined working regulations, the driving rule etc. The problem is formulated as a mixed integer linear program and treated by a multilevel variable neighborhood search algorithm. The method is implemented and tested on real-life data involving up to 2000 orders. It is shown that the method is able to provide solutions of good quality within reasonable running time.