A Decentralized Coordination Algorithm for a Highly Dynamic Vehicle Routing Problem
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
The Dynamic Vehicle Routing Problem (DVRP) involves a combinatorial optimization problem where new customer demands become known over time, and old routes must be reconfigured to generate new routes while executing the current solution. We consider the high level of dynamism problem. An application of highly dynamic DVRP is the ambulance service where a patient contacts the service center, followed by an evaluation of case severity, and a visit by a practitioner/ ambulance is scheduled accordingly. This paper considers a variant of the DVRP and proposes a decentralized algorithm in which collaborators (Depot and Vehicle), both have only partial information about the entire system. The DVRP is modeled as a periodic re optimization of VRP using the proposed decentralized algorithm where collaborators exchange local information to achieve the best global objective for the current state of the system. We assume the existence of a dispatcher e.g., headquarter of the company who can communicate to vehicles in order to gather information and assigns the new visits to them. The effectiveness of the proposed decentralized coordination algorithm is further evaluated using benchmark data given in literature. The results show that the proposed method performed better than the compared algorithms which utilize the centralized coordination in 12 out of 21 benchmark problems.
Abstract
The Dynamic Vehicle Routing Problem (DVRP) involves a combinatorial optimization problem where new customer demands become known over time, and old routes must be reconfigured to generate new routes while executing the current solution. We consider the high level of dynamism problem. An application of highly dynamic DVRP is the ambulance service where a patient contacts the service center, followed by an evaluation of case severity, and a visit by a practitioner/ ambulance is scheduled accordingly. This paper considers a variant of the DVRP and proposes a decentralized algorithm in which collaborators (Depot and Vehicle), both have only partial information about the entire system. The DVRP is modeled as a periodic re optimization of VRP using the proposed decentralized algorithm where collaborators exchange local information to achieve the best global objective for the current state of the system. We assume the existence of a dispatcher e.g., headquarter of the company who can communicate to vehicles in order to gather information and assigns the new visits to them. The effectiveness of the proposed decentralized coordination algorithm is further evaluated using benchmark data given in literature. The results show that the proposed method performed better than the compared algorithms which utilize the centralized coordination in 12 out of 21 benchmark problems.
참고문헌 (33)
- Azi, N., "A dynamic vehicle routing problem with multiple delivery routes", Annals of Operations Research, 199(1), pp.103~112 (2012)
- Barkaoui, M., "An adaptive evolutionary approach for real-time vehicle routing and dispatching", Computers and Operations Research, 40(7), pp.1766~1776 (2013)
- Beaudry, A., "Dynamic transportation of patients in hospitals", OR Spectrum, 32(1), pp.77~107 (2010)
- Bent, R. W., "Scenario-based planning for partially dynamic vehicle routing with stochastic customers", Operations Research, 52(6), pp.977~987 (2004)
- Chen, Z. -L., "Dynamic column generation for dynamic vehicle routing with time windows", Transportation Science, 40(1), pp.74~88 (2006)
- Christofides, N., "The period routing problem", Networks, 14(2), pp.237~256 (1984)
- Coslovich, L., "A twophase insertion technique of unexpected customers for a dynamic dial-a-ride problem", European Journal of Operational Research, 175(3), pp.1605~1615 (2006)
- Dan, B., "Dynamic optimization model and algorithm design for emergency materials dispatch", Mathematical Problems in Engineering (2013)
- Demirtas, Y.E, "A particle swarm optimization for the dynamic vehicle routing problem, In Modeling, Simulation, and Applied Optimization (ICMSAO)", 2015 6th International Conference on IEEE, pp.1~5 (2015)
- Elhassania, M. J., "A New Hybrid Algorithm to Solve the Vehicle Routing Problem in the Dynamic Environment", International Journal of Soft Computing, 8, pp.327~334 (2013)
- Euchi, J., "The dynamic vehicle routing problem : Solution with hybrid metaheuristic approach", Swarm and Evolutionary Computation, 21, pp.41~53 (2015)
- Fisher, M. L., "A generalized assignment heuristic for vehicle routing", Networks, 11(2), pp.109~124 (1981)
- Gendreau, M., "Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries", Transportation Research Part C : Emerging Technologies, 14(3), pp.157~174 (2006)
- Gendreau, M., "Parallel tabu search for real-time vehicle routing and dispatching", Transportation Science, 33(4), pp.381~390 (1999)
- Hanshar, F. T., "Dynamic vehicle routing using genetic algorithms", Applied Intelligence, 27, pp.89~99 (2007)
- Ichoua, S., "Diversion issues in real-time vehicle dispatching", Transportation Science, 34(4), pp.426~438 (2000)
- Ichoua, S., "Exploiting knowledge about future demands for real-time vehicle dispatching", Transportation Science, 40(2), pp.211~225 (2006)
- Ichoua, S., "Vehicle dispatching with time-dependent travel times", European Journal of Operational Research, 144(2), pp.379~396 (2003)
- Kergosien, Y., "A tabu search heuristic for the dynamic transportation of patients between care units", European Journal of Operational Research, 214(2), pp.442~452 (2011)
- Khouadjia, M. R., "A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests", Applied Soft Computing, 12(4), pp.1426~1439 (2012)
- Dynamic VRPs :a study of scenarios, "Kilby, P.", University of Strathclyde, ~, pp.Technical report APES-0-1998 (1998)
- Larsen, A., "Partially Dynamic Vehicle Routing-Models and Algorithms", The Journal of the Operational Research Society, 53(6), pp.637~646 (2002)
- Montemanni, R., "Ant colony system for dynamic vehicle routing problem", Journal of Combinatorial Optimization, 10, pp.327~343 (2005)
- Pillac, V., "A review of dynamic vehicle routing problems", European Journal of Operational Research, 225(1), pp.1~11 (2013)
- Schilde, M., "Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem", European Journal of Operational Research, 238(1), pp.18~30 (2014)
- Sheridan, P. K., "The dynamic nearest neighbor policy for the multi-vehicle pick-up and delivery problem", Transportation Research Part A : Policy and Practice, 49, pp.178~194 (2013)
- Shrimpf, G., "Recording breaking optimization results using the ruin and recreate principle", Journal of Computational Physics, 159, pp.139~171 (2000)
- Taillard, E., "A tabu search heuristic for the vehicle routing problem with soft time windows", Transportation Science, 31(2), pp.170~186 (1997)
- Taillard, E., "Parallel iterative search methods for vehicle routing problems", Networks, 23(8), pp.661~673 (1993)
- Taillard, E. D., "Adaptive memory programming : A unified view of metaheuristics", European Journal of Operational Research, 135(1), pp.1~16 (2001)
- Van Hemert, J. I., "Parallel Problem Solving from Nature-PPSN VIII" (2004)
- Yang, J., "Multi-Objective Distribution Model and Algorithm for Online Shopping Express Logistics", Journal of Computers, 8(10), pp.2558~2564 (2013)
- Zhu, K.Q., "A reactive method for real time dynamic vehicle routing problem", 2000 IEEE 24th International Conference on Tools with Artificial Intelligence (2000), IEEE Computer Society