Vehicle Routing Problem

Vehicle Routing Problem is combinatorial optimization problems which generally aim to find the optimal route for delivery packages to customer. This distribution problem usually starts form the depot to the destination point and then return to the depot. The most optimal route is the one that has the minimum operation or distribution cost. Process of searching route with the minimum cost becomes more complex since there are other constraints that should also be fulfilled.

Vehicle Routing Problem,

Consist of One Depot and Some Destination Point

VRP is not only a problem of land transportation modes, but also has evolved into the sea and air transportation mode. For example of land transportation mode, VRP is typically experienced by soft drink company which has to deliver the filled bottles and pick up the empty bottles from the customer. Figure above shows the illustration for this example problem. The entire filled bottle was initially come from the factory (the purple point) and it has to be delivered to their customers (the green points). With tens or even hundreds of destination addresses that should be visited, the order of delivery routes will greatly affect the fuel consumption and truck capacity. In this case, picking the most optimal route is very helpful to minimize the distribution cost.

VRP was first formally introduced by Dantzig and Ramser in 1959[1]. They described a real-world application concerning the delivery of gasoline to service station and proposed the first mathematical programming formulation and algorithmic approach. Later, another type and classification of VRP continue to grow and become more specific due to development of vehicles’ type used and another various customer demand. My research is focus on solving vehicle routing problem with simultaneous pickup and delivery (VRPSPD) type.  

VRP is included into combinatorial optimization which is specified by a finite set of solutions S and a cost function f that assigns a numerical value to each solution: f : S → R [19]. With the size of its solution space, it is not impossible, but very exhaustive to solve VRP using Brute Force method or linear programming. Heuristic method is very much used to solve this kind of problem. Heuristic are used to speed up the process of finding a good enough solution, where an exhaustive search is impractical. The most fundamental heuristic is trial and error, which can be used in everything including this VRP case. By using heuristics, time can be reduced when solving problems. 

There are several variations of the vehicle routing problem:
a. Vehicle Routing Problem with Time Windows (VRPTW): The delivery locations have time windows within which the deliveries (or visits) must be made.   
b. Capacitated Vehicle Routing Problem (with or without Time Windows): CVRP or CVRPTW. The vehicles have limited carrying capacity of the payloads that must be delivered. 
c. Vehicle Routing Problem with Pickup and Delivery (VRPPD): A number of payload need to be moved from certain pickup locations to other delivery locations. 
d. Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD): almost the same as VRPPD yet pickup and delivery processes is done simultaneously. 
e. Vehicle Routing Problem with LIFO (VRP Last in First Out): Similar to the VRPPD, except that an additional restriction is placed on the loading of the vehicles: at any delivery location, the item being delivered must be the item most recently picked up. This scheme reduces the loading and unloading times at delivery locations because there is no need to temporarily unload items other than the ones that should be dropped off.

My research discusses VRP with Simultaneous Pickup and Delivery problem. Generally this type handles pickup and delivery problems that are done simultaneously at each point. The constraints used are vehicle capacity and specification (such as maximum range of vehicle) and this case only can handles pickup and delivery demands from base point to destination points or the reverse. Whereas the movement between two destination points is not considered in this research.  

Since VRP was introduced 50 years ago, hundreds of studies have been done to find a better method to produce the most optimal solution. One of the simplest methods to solve VRP is Brute Force Method. This method works by generating all the combination possibilities, and pick the best one. However this method can only be used for simple problem with few numbers of destination point and constraint. This is because when the problem becomes large and complex, the solution scope will be even greater and needed a long time to generate and count all those possibilities.

Other methods currently being actively developed is a heuristic method. This method can handle a very large and complex problem with more effective computation time. Some examples of heuristic method that can be used to solve VRP problems are nearest neighbor algorithm, random path change algorithm, genetic algorithm, simulate annealing, column generation, tabu search, etc.

A method that is used in my research is Genetic Algorithm. Genetic Algorithm is an optimization method that inspired by natural behavior. GA uses several supporting algorithm to find solutions which are constantly enhanced until the best solution is finally found. Unlike Brute Force method which generate all possibility, GA find the best solution within just generating some numbers of possibility solution randomly—called population—one times, then apply the supporting algorithm (such as crossover, mutation, etc) to make a new numbers of possibility which have better solution than it first population. The best solution will stay until there is another solution which has a better value to replace it. So at the end of the process, the obtained solution is the one with the best value among all possibility solution that have been raised. Detail explanation about GA will be discussed in the next post. 

Source: 
Carry Prameswari (2011)
Final Project Report - Literature Study
Solving Vehicle Routing Problem with Simultaneously Pickup and Delivery using Genetic Algorithm and Prins Splitting Procedure 

Reference: 
[1] G. B. Dantzig and J. H. Ramser. 1959. “ The truck dispatching problem, Management Science”.
[19] Thierens, Dirk.  “Metaheuristic Search for Combinatorial Optimization”. Universiteit Utrecht The Netherlands.