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

Introduction

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:

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: