Studies in Informatics and Control – ICI Bucharest
Solving Dynamic Vehicle Routing: An Alternative Metaheuristic Approach
Amr BADR
Department of Computer Science, Faculty of Computers and Information
Cairo University
Abstract: An adapted Evolution strategy is proposed for solving the Dynamic (General) Vehicle Routing Problem (DVRP). Several Mutation and crossover operators are designed to deal with real-time demand information which is available only at the day of operation. A simulation was carried out in which intelligent planning of new online orders are dealt with. Several problems were generated to test the proposed algorithm. The problems were solved twice. First, they are solved off-line in which all orders are known prior to the day of operation. Second, they were solved in which orders are dynamic. The competitive ratio gave an average of 0.65.
Keywords: Dynamic Vehicle Routing; General Vehicle Routing; Adapted Evolution Strategy; Intelligent Real-time Planning.
Dr. Amr Badr is currently an Associate Professor of Computer Science at the Faculty of Computers and Information, Department of Computer Science, Cairo University. He received his BSc in Engineering with Honors. He received his MSc and PhD in Computer Science in 1995 and 1998 from Cairo University. He has published more than 50 Journal Research papers and is currently enrolled on the editorial boards of several international journals. His prime research interests are computational Intelligence, Bioinformatics and Medical imaging.
>Full text
CITE THIS PAPER AS:
Amr BADR, Solving Dynamic Vehicle Routing: An Alternative Metaheuristic Approach, Studies in Informatics and Control, ISSN 1220-1766, vol. 18 (2), pp. 159-164, 2009.
1. Introduction
Dynamic (General) Vehicle Routing Problem (DVRP) can be considered as a good example of a distribution context, because of the fact that intelligent manipulation of real-time information can distinguish between one company and another by superior on-time service. Problems of both generic vehicle routing (V. R. P.) and dynamic vehicle routing (DVRP) are identical. But in VRP all routing and demand information are certainly known prior the day of operation; whereas in DVRP part or all of the necessary information is available only at the day of operation. Significance of DVRP is crystallized by the variety of environments it can model. Additional assets are the transportation of elderly or physically handicapped and emergency services (e.g. police, fire and ambulance dispatching).
The paper is organized as follows: Section 2 gives the previous researches using meta-heuristics. The mathematical formulation of the problem is in section 3. The proposed mutation and crossover operators are explained in section 4 and 5. The proposed algorithm is forwarded in section 6 and simulation and results in section 7.
8. Conclusion
An adapted Evolution Strategy is forwarded with operators specially designed to solve the real-time dynamic (general) vehicle routing problem. Not all of the orders were known prior to the day of distribution. This incurred the intelligent dynamic planning and re-planning of routes (tours). Several test problems were generated and solved both by an offline suitable algorithm and the proposed real-time algorithm giving an average of 65% competitive ratio.
References:
- Braysy, O. and M. Gendreau, Vehicle Routing Problem with Time Windows, Part I: Rout Construction and Local Search Algorithms. Transportation Science, 39(1):104-118, 2005.
- Braysy, O. and M. Gendreau, Vehicle Routing Problem with Time Windows, Part II Meta-heuristics. Transportation Science, 39(1):119-139, 2005.
- Gruhn, Goel and V., A General Vehicle Routing Problem, European Journal of Operational Reasearch,191(3): 650-660, 2008.
- Beyer, Hans-George, The Theory of Evolution Strategies, Springer. 2001.
- Kirkpatrick, S. C., D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing, Science, 220 (4598): 671 – 680, 1983.
- Mitrovie-Minic, S., The Dymanic Pickup and Delivery Problme with Time Windows, Ph.D thesis, School of Computing Science, Simon Fraser University, Burnaby, BC, Canada, 2001.
- Montemanni, R., L. M. Gambardella, A. E. Rizzoli and A. V. Donati, A New Algorithm for a Dynamic Vehicle Routing Problem Based on Ant Colony System, Tech report IDSIA-23-02, Instituto Dalle Molle di Studi sull’Intelligenza Artificiale (IDSIA), Lugano, Switzerland, 2002.
- Pankratz, G., Dynamic Planning of Pickup and Delivery Operations by means of Genetic Algorthims, Diskussionsbeitrag Nr. 361, Fahbereich irtschaftswissenschaften, Fernuniversitat Hagen, Hagen, Germany, 2004.
- Polacek, M., R. F. Hartl, K. Doerner and M. Reimann, A Variable Neighborhood Search for the Multi depot Vehicle Routing Problem with the Time Windows, Journal of Heuristics, 10 : 613- 627, 2004.
- Ropke, S. and D. Pisinger, An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows, Transportation Science 40(4): 455- 472, 2006.
- Schrimpf, G., J. Schneider, H. Stamm-Wilbrandt, and G. Dueck, Record Breaking Optimization Results Using The Ruin and Recreate Principle, Journal of Computational Physics, 159:139 – 171, 2000.
- Sleator, D. and R. E. Tarjan, Amortized efficiency of List Update and Paging Rules, Communications of the ACM 28(2):202-208, 1985.
- Taillard, E. D., L. M. Gambardella, M. Gendreau, and J.-Y. Potvin, Adaptive Memory Programming: A Unified View of Meta-Heuristics, Tech Report IDSIA-19-98, Istituto Dalle Molle Di Studi Sull Intelligenza Artificiale (IDSIA), Lugano, Switzerland, 1998.