Multi Depot Probabilistic Vehicle Routing Problems with a Time Window: Theory, Solution and Application

Multi Depot Probabilistic Vehicle Routing Problems with a Time Window: Theory, Solution and Application

Sutapa Samanta (Maryland State Highway Administration, USA) and Manoj K. Jha (Morgan State University, USA)
DOI: 10.4018/978-1-4666-2038-4.ch053
OnDemand PDF Download:


Vehicle Routing Problems (VRPs) are prevalent in all large pick up and delivery logistics systems and are critical to city logistics operations. Of notable significance are three key extensions to classical VRPs: (1) multi-depot scenario; (2) probabilistic demand; and (3) time-window constraints, which are considered simultaneously with VRPs in this paper. The issue then becomes a Multi Depot Probabilistic Vehicle Routing Problem with a Time Window (MDPVRPTW). The underlying complexities of MDPVRPTW are analyzed and a heuristic approach is presented to solve the problem. Genetic algorithms (GAs) are found to be capable of providing an efficient solution to the so-called MDPVRPTW. Within the GAs, two modification operators namely, crossover and mutation, are designed specially to solve the MDPVRPTW. Three numerical examples with 14, 25, and 51 nodes are presented to test the efficiency of the algorithm as the problem size grows. The proposed algorithms perform satisfactorily and the limiting case solutions are in agreement with the constraints. Additional work is needed to test the robustness and efficiency of the algorithms as the problem size grows.
Chapter Preview


The Vehicle Routing Problem (VRP) has received widespread attention in recent years because of its applicability in many pickup and delivery systems. Multiple depots become necessary for systems consisting of larger networks, such as for the operation of larger logistics systems of distribution companies. When the vehicle routing problem involves multiple depots, it is called a Multi Depot Vehicle Routing Problem (MDVRP). In such problems the number of vehicles can be equal to or exceed the number of depots. In most of the real-life VRPs, demands at the customer nodes vary due to various factors, such as locational and temporal seasonal factors. Hence, the stochasticity has to be considered for the demands at the customer nodes. The vehicle routing problem which considers stochastic demands of the customers, is called Probabilistic Vehicle Routing Problem (PVRP). Another important criterion for any logistics system is to provide the service within a specified time period. Hence, the time window concept is associated with the VRPs, which is coined as Vehicle Routing Problem with Time Window (VRPTW).

The real life vehicle routing problem with a larger network can have all the issues mentioned above, such as the nodes can have variable or stochastic demand, the services have to be provided within fixed time periods at the nodes and multiple depots are needed to cover the network. Hence all the three components are important for a vehicle routing problem The proposed MDPVRPTW is complex in nature as it combines all the three problems, such as, VRPTW, MDVRP, and PVRP. There are many applications of this type of problem like the pick-up of children by school buses, garbage collection, delivery of laundry, and delivery by United Postal Services (UPS). The problem in all these cases can be described as follows:

A set of customers in an area has to be provided with a service by a fleet of vehicles. The vehicles will start from a set of depots to cover larger areas. Each node or point has a demand, which varies stochastically and must be picked up by any of the vehicles. The customers specify a period of time in which the pick up must occur. This particular time period is called the time window. The vehicles have specific limited capacities. The total demand picked up by each vehicle should not exceed its corresponding capacity. The objective is to find out a set of routes formed by the fleet of vehicles in order to cover these customers in such a way that total travel cost becomes minimum while satisfying the capacity and time window constraints.

Previous researchers have approached various components of MDPVRPTW separately. The stochasticity in demand, the time window constraint, and the multidepot scenario is either addressed individually or in the combination of two in most of the cases. As the number of variants increase with the introduction of each component, it becomes difficult to devise an analytical approach to obtain an optimal solution. This might be the reason for the MDPVRPTW to be unsolved, to date. The earlier works in the area have not addressed all the three components of the vehicle routing problem together, but in real life problems, they exist together in most cases. The attempt in this study is to develop an innovative algorithm, which is capable of handling these three components simultaneously and is able to produce reasonable results. The algorithm can be modified and improved further in future; nevertheless, it provides a good start to handle the different components of the VRP that make the problem relatively complex to solve. The new heuristic-based algorithm to solve the MDPVRPTW is developed after carefully scrutinizing significant earlier works and the underlying complexities associated with the problem.

In the next section, we briefly review the VRP literature. The third section describes the formulation and the proposed methodology to solve the MDPVRPTW. The last section presents three numerical examples of growing complexity. Sensitivity of the results on the problem domain is examined by relaxing or restricting the time window constraint so that the results can be validated by justifying them within the specified boundaries.


Literature Review

This section reviews various methodologies developed by the researchers to solve different components of the MDPVRPTW at different times. A selective list of literature review has been presented here. The various studies available in the literature can be broadly categorized as follows:

Complete Chapter List

Search this Book: