Metaheuristics for The Solution of Dynamic Vehicle Routing Problem With Time Windows (DVRPTW) With Travel Time Variable

Nurlita Gamayanti

Abstract

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.

Full Text:

PDF

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

Refbacks

  • There are currently no refbacks.