Rich Vehicle Routing Problems and Applications

Project Abstract

<p>               <b>ABSTRACT&nbsp;</b></p><p>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 consoli- ii dation 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. <br></p>

Project Overview

<p> Introduction&nbsp;</p><p>This introductory chapter provides the background, motivation, and overview of this thesis. The main topic, the Vehicle Routing Problem (VRP), is first introduced. The purpose and contribution of this work are then given, followed by the outline of this thesis.&nbsp;</p><p><b>1.1 Motivation&nbsp;</b></p><p>Transportation plays an important role in our daily life. In the US, the transportation related goods and services contributed $1156 billion, or around 11% of GDP1. In 2003, within EU 2184 billion tonne-kilometers transport was performed, in which the road freight accounts for 72%. The amount of road freight has increased by 38% from 1995 to 20052. Since even a small percentage saving will yield a substantial saving in the transportation cost research on VRP that deals with minimization of the road freight cost, has become a very important area. Moreover, the growth of transport-related energy consumption and its negative effects on environment have attracted more and more worldwide.&nbsp;In the US, transport-related energy consumption increased from 516 million tonnes in 1971 to 745 million tonnes in 2002 (growth of 44%). Between 1970 and 2002, CO2 emissions from the transport sector in the US increased by 69%.3 Therefore, research on VRP not only reduces the transportation cost but also contributes to the environmental protection. During the past decades, considerable research on vehicle routing and scheduling problems has been carried out. One of the earliest and also the simplest routing problem is the Traveling Salesman Problem (TSP), in which the shortest tour to visit a number of cities must be determined for a salesman who starts from and terminates at the same city. Figure 1.1 shows an example of the TSP.&nbsp;</p><p>This problem was later extended to the Multiple Traveling Salesman Problem (mTSP), in which there are multiple salesmen and they all start at and return to the same city, which is referred to as the depot. In the late fifties, Dantzig and Ramser (1959) introduced the VRP, which can be viewed as an m-TSP with customer demands and vehicle capacity. An example of such a VRP is shown in Figure 1.2. The VRP introduced in Dantzig and Ramser (1959), strictly speaking, is called Capacitated Vehicle Routing Problem (CVRP), and is one of the simplest vehicle routing problems. During the past five decades, various solution methods have been proposed for solving the CVRP. Some of these methods can lead to optimal solutions and are therefore named exact methods. These methods include Branch-and-Bound (B&amp;B), Branch-andCut (B&amp;C) and Branch-and-Price (B&amp;P). The exact methods can only solve the problem of a limited size because the computational complexity of the VRP is very high. The most sophisticated exact algorithms today can solve instances involving a little more than one hundred customers. One of such an algorithm is presented in Baldacci et al. (2008b). Since most of the real-life applications consist of hundreds or even thousands of customers, the research of the VRP has been largely focusing on the development of approximate solution techniques that can provide high-quality solutions, though not necessarily the optimal ones, within short or acceptable computational times. Heuristics are one kind of such methods that generate good solutions in an iterative fashion. The earliest heuristic methods were proposed to construct a feasible solution from scratch. Later developments on heuristics emphasized how to improve a solution by modifying the solution, such as relocating a customer from one route to another. Since the late eighties, special attention has been devoted to metaheursitics, a class of sophisticated heuristics that often combines construction heuristics and improvement heuristics based on concepts derived from artificial intelligence, biology, mathematics, physics or nature, and generally provides solutions that are much better than those obtained by other heuristics. During the last two decades, metaheursitics have been successfully applied to many large-scale complicated vehicle routing problems and provided solutions that can hardly be obtained by manual planning or simple heuristics. Cities Travel route Salesman Figure 1.1: An example of the TSP. Each city must be visited once. Given the large potential savings that have been shown by the research on VRP, many industrial distributors have become more and more interested in optimizing their distribution in practice. This increasing interest can be observed by the large number of logistic consultant companies that provide the distributors with tools or software for planning and optimizing distribution and transportation problems based on OR techniques. However, real-life route planning problems usually involve a large number of practical constraints. To this end, research interest in the VRP field has also been extended from the idealized VRP to variants of the VRP, called Rich Vehicle Routing Problem (RVRP). These problems are characterized by high complexity and large data size, and hence are much more challenging than the CVRP (Hasle et al. (2006)). One of the well-known RVRPs is the Vehicle Routing Problem with Time Windows (VRPTW), where each customer is associated with a time interval, called time window, within which, the customer must be visited. This kind of time restrictions is often imposed by real-life applications, such as the school bus route planning. Another type of the RVRP, called Heterogeneous Vehicle Routing Problem (HVRP), extends the VRP by considering the planning of heterogeneous vehicles.&nbsp;</p><p>A third extension, Multi-Depot Vehicle Routing Problem&nbsp; Introduction Customers Depot Vehicles Route Figure 1.2: An example of the VRP. There are 16 customers with unit demand and four vehicles with capacity 5. (MDVRP), covers multiple depots, which are quite common in the distribution network of global distributors. Another example of the RVRP is the Dynamic Vehicle Routing Problem (DVRP), in which customers are revealed incrementally over time rather than known in advance. The studies on DVRP provide the possibility of on-line planning in real life. Most of these RVRPs considered in the literature are still over-simplified since they only consider one or a few practical issues. A practical routing problem is often a mixture of these RVRPs. To close the gap between the RVRPs in academic research and in industry, a strong trend in studying richer models can be observed in the recent years.&nbsp;</p><p><b>1.2 Purpose and contributions of thesis&nbsp;</b></p><p>The purpose of this thesis is to study the RVRPs that involve complicated practical constraints arising in real life. These RVRPs share common characteristics: they are usually large-scale, involving up to hundreds or even thousands of customers; they are very complicated and impose a lot of practical constraints.&nbsp;</p><p><b>1.3 Outline of thesis&nbsp;</b></p><p>&nbsp;Due to the high complexity of these problems, we focus on solving them by metaheuristics in this work. The main contribution of this work is the development and implementation of three metaheuristics for solving three large-scale complicated real-life RVRPs. The proposed methods are, when experimentally investigated, prove to be efficient and effective. The outcome of the research on the three problems shows that metaheuristics are capable of providing good solutions to hard and complex planning problems in real life. The three papers of the thesis are produced based on the research results. Additionally, comprehensive introductions and reviews of the VRP and the RVRP are presented.&nbsp;</p><p><b>1.3 Outline of thesis&nbsp;</b></p><p>The remainder of this thesis is organized as follows. Chapter 2 presents the mathematical formulation of the CVRP, and briefly discusses the complexity issues. A review of the solution methods for the CVRP is also given. Chapter 3 addresses the practical issues arising in real-life routing problems and the keys to the development of metaheuristics for these problems. A number of important RVRPs that are relevant for this work are introduced and briefly reviewed. Chapter 4 summarizes the papers included in this thesis, followed by conclusions in Chapter 5. Finally, the three papers are provided in the Appendix. <br></p>