Metaheuristics for The Solution of Dynamic Vehicle Routing Problem With Time Windows (DVRPTW) With Travel Time Variable
DOI:
https://doi.org/10.12962/j25796216.v1.i1.13Abstract
This research is focusing on the development of metaheuristic algorithm to solve Dynamic Vehicle Routing Problem With Time Windows (DVRPTW) for the service provider of Inter-city Courier. The algorithm is divided into two stages which is static stage and dynamic stage. In the static stage, modified Ant Colony System is developed and in the dynamic stage, Insertion Heuristic is developed. In DVRPTW, vehicle’s routes are raised dynamically based on real time information, for example the reception of new order. To test the performances of the developed metaheuristic algorithm, the author compares the developed algorithm with the nearest neighbor algorithm and with the combination between the nearest neighbor and insertion heuristics algorithm. Experiment is done using Chen’s standard data test. The developed metaheuristic algorithm was applied on the network data of the roads in Surabaya, where the routes generated not only determine the order that the consumer must visit but also determine the routes that must be passed. After the experiment, the author conclude that the developed algorithm generates a better travel time total than the nearest neighbor and the combination between the nearest neighbor and insertion heuristics and can also generate route dynamically to respond to the new order well.
Keywords: Inter-City Courier, Dynamic Vehicle Routing Problem dengan Time Window (DVRPTW), Ant Colony System, Insertion Heuristics
References
Champbell,A.M., Martin S (2004), “Efficient Insertion Heuristics for Vehicle Routing and Schdulling Problems”.
Chen, C.H., Ting, C.J. (2004), “ An Improved Ant Colony Systems Algorithm for The Vehicle Routing Problem”, Working Paper 2004-001, Department of Industrial Engineering and Management, Yuan Ze University, Taiwan.
Chen, C.H., Ting, C.J. (2005), “A Hybrid Ant Colony System for Vehicle Routing Problem with Time Windows,” Journal of the Eastern Asia Society for Transportation Studies, Vol.6, pp.2822-2836.
Donati, Gambardella,M., Rizzoli, A.E.,Casagrande,N.,Montemanni, R. (2002), “Time Dependent Vehicle Routing Problem with an Ant Colony System,” Instituto Dalle Molle di Studi sull’Intelligenza Artificiale (IDSIA).
Gambardella,L.M., Dorigo,M. (2000), “ An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem,” INFORMS Journal on Computing Vol.12, No.3.
Gambardella, L.M, Tai, E., Agazzi, G.,”A Multiple Ant Colony System for Vehicle Routing Problem with Time Window”, McGraw Hill, London
Gendreau, M., Guertin, F., Potvin, J., Seguin, “ Neighborhood Search Heuristic for a Dynamic Vehicle Dispatching Problem with Pick-Up and Delivery”, Universite de Montreal
Gendreau, M., Guertin, F., Potvin, J., Taillard, E. (1999) ,”Parallel Tabu Search for Real Time Vehicle Routing and Dispatching”, Transportation Sience, 33(4):381-390
Ichoua, S., Gendreau, M., Potvin, J. (2000),”Diversion Issues in Real Time Vehicle Dispatching”, Transportation Science, 34(4):426-438
Kim,S., Lewis,M.E., Chelsea C.White III, “ Dynamic Vehicle Routing with Real-Time Traffic Information,” In Proceedings of the 10th World Congress on Intelligent Transport Systems, Madrid, Spain.
Kim,S., Lewis,M.E., Chelsea C.White III, “ Dynamic Vehicle Routing with Real-Time Traffic Information,” IEEE Transactions on Intelligent Transportation Systems, Vol.6, No.2.
Montemanni, R.,Gambardella, L.M., Rizolli, A.E., Donati, A.V, “Instituto Dalle Molle Studi sull’Intelligenza Artificiale (IDSIA), “A New Algorithm for a Dynamic Vehicle Routing Problem based on Ant Colony System”
Renaud, J., Boctor, F.F., Ouennice,J., (1998), “A Heuristics for The Pick Up and Delivery Traveling Salesman Problem.
Uchimura, K., Takahashi, H., Saitoh, T. (2002), “Demand Responsive Services in Hierarchical Public Transportation System”,IEEE Transactions on Vehicular Technology, Vol. 51, No. 4, pp 1-6
Downloads
Published
Issue
Section
License
Copyright
Submission of a manuscript implies that the submitted work has not been published before (except as part of a thesis or report, or abstract); that it is not under consideration for publication elsewhere; that its publication has been approved by all co-authors. If and when the manuscript is accepted for publication, the author(s) still hold the copyright and retain publishing rights without restrictions. Authors or others are allowed to multiply article as long as not for commercial purposes. For the new invention, authors are suggested to manage its patent before published. The license type is CC-BY-NC 4.0.
Disclaimer
No responsibility is assumed by publisher and co-publishers, nor by the editors for any injury and/or damage to persons or property as a result of any actual or alleged libelous statements, infringement of intellectual property or privacy rights, or products liability, whether resulting from negligence or otherwise, or from any use or operation of any ideas, instructions, procedures, products or methods contained in the material therein.
