Abstract
Vehicle Routing Problem (VRP), a well-known combinatorial optimization problem had been presented by Dantzing and Hamser in 1959. The problem has taken its inspiration from the transport field. In real field environment, a lot of variants of the problem exist that actually belongs to the class of NP-hard problem. Dynamic Vehicle routing problem (DVRP) is one of the variant of VRP that varies with respect to time. In DVRP, new customer orders appear over time and new route must be reconfigured at any instantaneous time. Although, some exact algorithms such as dynamic programming methods, branch and bound etc. can be applied to find the optimal route of a smaller size VRP. But, These Algorithms fail to give the solution of existed model of VRP in real field environment under given real time constraints. Courier services, dial a ride services and express mail delivery etc. are the few examples of real field environment problems that can be formulated in the form of DVRP. In this chapter, A novel variants of DVRP named as DVRP with geographic ranking (DVRP-GR) has been proposed. In DVRP-GR, geographical ranking, customer ranking, service time, expected reachability time, customer satisfaction level have been optimized. A solution of DVRP-GR using seed based particle swarm optimization (S-DVRS-PSO) has been also proposed. The simulations have been performed using customized simulator developed in C++ environment. The data sets used in the simulations are OMK-01, OMK-02 and OMK-03 generated in real vehicular environment. The solution of the proposed algorithm has been compared with the randomized solution technique. Analysis of the simulation results confirms the effectiveness of the proposed solution in terms of various parameters considered viz. number of vehicles, expected reachability time, profit and customer satisfaction.
TopIntroduction
Recently, Intelligent Transport System (ITS) has diversified the application area of Dynamic Vehicle Routing Problem (DVRP) enormously. E-commerce, print media, medical, public transportation, oil sector are only few examples (Golden, Raghavan, & Wasil, 2008). DVRP is an extension of traditional Vehicle Routing Problem (VRP) in terms of complexity. The traditional VRP can be symbolically stated on a connected network 
, where 
indicates the set of nodes; 
represents the set of connections and 
denotes communication cost matrix defined over CS. Traditionally, the node n0 is the central depot from where all the vehicles start and end their services. The remaining nodes of NS denotes the customers spread over geographically distinct locations. The VRP is nothing but finding a set of routes for a given set of vehicles such that each vehicles visit the customers exactly once and overall travel cost of the vehicles should be minimum (Lin, Choy, Ho, Chung, & Lam, 2014). An example of traditional VRP has been illustrated in Figure 1. The central depot has four delivery vehicles to serve the demands of four customers. According to the availability of the routes, the routes for delivery vehicles have been planned.
Figure 1. The traditional Vehicle Routing Problem (VRP)
Due to the recent technological advances in real time communication, the shape of VRP has been changed as DVRP (cf. Figure 2). A number of variants of VRP have been explored as DVRP by incorporating different set of constraints in traditional VRP (Pillac, Gendreau, Guéret, & Medaglia, 2013). The most common variants have been illustrated following.
Figure 2. Dynamic Vehicle Routing Problem (DVRP)
- 1.
VRP with Pick and Delivery (VRP-PD): A given set of goods have to be transported from some pick-up locations to the delivery locations. It means, no central depot for vehicles is required.
- 2.
Capacitated VRP (C-VRP): Vehicles with pre-specified but same goods carrying capacity.
- 3.
Heterogeneous VRP (H-VRP): Vehicles with pre-specified but different goods carrying capacity.
- 4.
VRP with Last-In-First Out (VRP-LIFO): The items that have been picked up most recently must be the items that have to be delivered in the next delivery locations.
- 5.
VRP with Time Window (VRP-TW): Each delivery locations must be visited during a pre-specified time interval.
- 6.
Open VRP (O-VRP): The vehicles are not required to return to the central depot after visiting all the assigned customers.
- 7.
Dial A Flight VRP (DAF-VRP): Public transport through airline has been also studied as one of the variants of VRP.
- 8.
Dial A Ride VRP (DAR-VRP): The normal public transport problem.
- 9.
VRP with Multiple Trips (VRP-MT): The vehicles can take more than one delivery tour once it finishes the assigned tour.