×

Development and implementation of algorithms for vehicle routing during a no-notice evacuation. (English) Zbl 1426.90041

Summary: This article develops and implements time-dependent shortest path and assignment algorithms for vehicle routing and assignment during a no-notice evacuation. A time-dependent shortest path algorithm with arc labeling is designed to improve computer storage space efficiency. Visual Basic for Application (VBA) is used to improve time efficiency of both shortest path and assignment algorithms. Performance of the algorithms is analyzed and compared through implementation in VBA and the General Algebraic Modeling System (GAMS). Since VBA seamlessly integrates with Microsoft Excel and enables efficient data manipulation, the algorithms implemented in VBA are more efficient and obtain optimal solutions faster than those implemented in the GAMS. The shortest path algorithm with arc labeling implemented in VBA may be used for real-time vehicle routing for large road networks during no-notice evacuations.

MSC:

90B06 Transportation, logistics and supply chain management
90C35 Programming involving graphs or networks

Software:

Excel; Visual Basic; GAMS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Almoustafa, S.; Hanafi, S.; Mladenović, N., New exact method for large asymmetric distance-constrained vehicle routing problem, European Journal of Operational Research, 226, 386-394 (2013) · Zbl 1292.90242 · doi:10.1016/j.ejor.2012.11.040
[2] Ando, N.; Taniguchi, E., Travel time reliability in vehicle routing and scheduling with time windows, Networks and Spatial Economics, 6, 293-311 (2006) · Zbl 1128.90308 · doi:10.1007/s11067-006-9285-8
[3] Andres Figliozzi, M., The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics, Transportation Research Part E: Logistics and Transportation Review, 48, 616-636 (2012) · doi:10.1016/j.tre.2011.11.006
[4] Balas, E.; Toth, P.; Lawler, L.; Lenstra, J. K.; Rinnooy Kan, A. H. G.; Shmoys, D. G., The traveling salesman problem, Branch and bound methods, 361-401 (1985), Chichester: Wiley, Chichester
[5] Barabasi, A. L., Linked: The new science of networks (2002), Cambridge, MA: Perseus, Cambridge, MA
[6] Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows, Part I: Route construction and local search algorithms, Transportation Science, 39, 104-118 (2005) · doi:10.1287/trsc.1030.0056
[7] Brinkhoff, T., A framework for generating network-based moving objects, GeoInformatica, 6, 153-180 (2002) · Zbl 1036.68643 · doi:10.1023/A:1015231126594
[8] Chen, H. K.; Hsueh, C. F.; Chang, M. S., The real-time time-dependent vehicle routing problem, Transportation Research Part E: Logistics and Transportation Review, 42, 383-408 (2006) · doi:10.1016/j.tre.2005.01.003
[9] Chen, B. Y.; Lam, W. H. K.; Sumalee, A.; Li, Q.; Shao, H.; Fang, Z., Finding reliable shortest paths in road networks under uncertainty, Networks and Spatial Economics, 13, 123-148 (2013) · Zbl 1332.90032 · doi:10.1007/s11067-012-9175-1
[10] Clarke, G.; Wright, J. V., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 568-581 (1964) · doi:10.1287/opre.12.4.568
[11] Dantzig, G. B.; Fulkerson, D. R.; Johnson, S. M., Solution of a large-scale traveling salesman problem, Operations Research, 2, 393-410 (1954) · Zbl 1414.90372
[12] Dreyfus, S. E., An appraisal of some shortest-path algorithms, Operations Research, 17, 395-412 (1969) · Zbl 0172.44202 · doi:10.1287/opre.17.3.395
[13] GAMS Development Corporation. (2013). GAMS Distribution 24.0.2. Retrieved from https://www.gams.com/
[14] Haghani, A.; Jung, S., A dynamic vehicle routing problem with time-dependent travel times, Computers & Operations Research, 32, 2959-2986 (2005) · Zbl 1071.90011
[15] Haimovich, M.; Rinnooy Kan, A. H. G.; Stougie, L.; Golden, B. L.; Assad, A., Vehicle routing: Methods and studies, Analysis of heuristic routing problems, 47-61 (1988), Amsterdam: North Holland, Amsterdam
[16] Ichoua, S.; Gendreau, M.; Potvin, J. Y., Vehicle dispatching with time-dependent travel times, European Journal of Operational Research, 144, 379-396 (2003) · Zbl 1012.90003 · doi:10.1016/S0377-2217(02)00147-9
[17] Jeong, H., Complex scale-free networks, Physica A: Statistical Mechanics and its Applications, 321, 226-237 (2003) · Zbl 1027.90501 · doi:10.1016/S0378-4371(02)01774-0
[18] Kaufman, D. E.; Smith, R. L., Fastest paths in time-dependent networks for intelligent vehicle-highway systems application, Journal of Intelligent Transportation Systems, 1, 1, 1-11 (1993)
[19] Kritzinger, S.; Doerner, K. F.; Hartl, R. F.; Kiechle, G. Ÿ.; Stadler, H.; Manohar, S. S., Using traffic information for time-dependent vehicle routing, Procedia—Social and Behavioral Sciences, 39, 217-229 (2012) · doi:10.1016/j.sbspro.2012.03.103
[20] Kuhn, H. W., The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, 2, 83-97 (1955) · Zbl 0143.41905 · doi:10.1002/(ISSN)1931-9193
[21] Laporte, G.; Nobert, Y.; Taillefer, S., A branch-and-bound algorithm for the asymmetrical distance-constrained vehicle routing problem, Mathematical Modelling, 9, 857-868 (1987) · Zbl 0634.90029 · doi:10.1016/0270-0255(87)90004-2
[22] Laporte, G.; Nobert, Y.; Taillefer, S., Solving a family of multi-depot vehicle routing and location-routing problems, Transportation Science, 22, 161-172 (1988) · Zbl 0662.90039 · doi:10.1287/trsc.22.3.161
[23] Lecluyse, C.; Van Woensel, T.; Peremans, H., Vehicle routing with stochastic time-dependent travel times, 4OR-Q Journal of Operations Research, 7, 363-377 (2009) · Zbl 1188.90032
[24] Maden, W.; Eglese, R.; Black, D., Vehicle routing and scheduling with time-varying data: A case study, Journal of the Operational Research Society, 61, 515-522 (2010) · Zbl 1196.90070 · doi:10.1057/jors.2009.116
[25] Montoya-Torres, J. R.; Franco, J. L.; Isaza, S. N.; Jiménez, H. F.; Herazo-Padilla, N., A literature review on the vehicle routing problem with multiple depots, Computers & Industrial Engineering, 79, 115-129 (2015)
[26] Pentico, D. W., Assignment problems: A golden anniversary survey, European Journal of Operational Research, 176, 774-793 (2007) · Zbl 1103.90060 · doi:10.1016/j.ejor.2005.09.014
[27] Rakha, H.; El-Shawarby, I.; Arafeh, M.; Dion, F., Proceedings of 2006 IEEE Intelligent Transportation Systems Conference, Estimating path travel time reliability, 236-241 (2006), Toronto
[28] Spliet, R.; Gabor, A. F., The time window assignment vehicle routing problem, Erasmus School of Economics (ESE), EI2012_07, 1-19 (2012)
[29] Van Woensel, T.; Kerbache, L.; Peremans, H.; Vandaele, N., Vehicle routing with dynamic travel times: A queueing approach, European Journal of Operational Research, 186, 990-1007 (2008) · Zbl 1146.90426 · doi:10.1016/j.ejor.2007.03.012
[30] Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., A unified solution framework for multi-attribute vehicle routing problems, European Journal of Operational Research, 234, 658-673 (2014) · Zbl 1304.90004 · doi:10.1016/j.ejor.2013.09.045
[31] Zare-Reisabadi, E.; Mirmohammadi, S. H., Site dependent vehicle routing problem with soft time window: Modeling and solution approach, Computers & Industrial Engineering, 90, 177-185 (2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.