Solving vehicle routing problem for multistorey buildings using iterated local search

Vehicle routing problem (VRP) which is a well-known combinatorial optimisation problem that has manyapplications used in industry is also a generalised form of the travelling salesman problem. In this study, we definedand formulated the VRP in multistorey buildings (Multistorey VRP) for the first time and proposed a solving methodemploying iterated local search metaheuristic algorithm. This variant of VRP has a great potential for turning thedirection of optimisation research and applications to the vertical cities area as well as the horizontal ones. Routes ofpart picking or placing vehicles/humans in multistorey plants can be minimised by this way. VRP can also be appliedto the optimisation of delivering the packages (goods, meals, folders, mails, etc.) to rooms or locations of the structuressuch as buildings, and skyscrapers for travelling robots/humans using elevators and stairs. The first detailed multistoreybuilding optimisation experiments were conducted by designing a series of scenarios with different parameter values(number of storeys, connections between storeys and customers). The results were presented and the effects of thevarious building structures over the performance were discussed.

PDF

___

[1] Dantzig GB, Ramser JH. The truck dispatching problem. MANAGE SCI 1959; 6: 80-91.
[2] Clarke G, Wright JW. Scheduling of vehicles from a central depot to a number of delivery points. OPER RES 1964; 12: 568-581.
[3] Gillett BE, Miller LR. A heuristic algorithm for the vehicle-dispatch problem. OPER RES 1974; 22: 340-349.
[4] Lin S. Computer solutions of the traveling salesman problem. The Bell System Technical Journal 1965; 44: 2245- 2269.
[5] Or I. Traveling Salesman-type combinatorial problems and their relation to the logistics of blood banking. PhD, Northwestern University, Evanston, USA, 1976.
[6] Osman IH. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. ANN OPER RES 1993; 41: 421-451.
[7] Holland JH. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Cambridge, MA, USA: MIT Press, 1992.
[8] Glover F. Tabu search part i. ORSA Journal on computing 1989; 1: 190-206.
[9] Feo TA, Resende MGC. Greedy randomized adaptive search procedures. Journal of global optimization 1995; 6: 109-133.
[10] Rechenberg I. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Stuttgart, Germany: Frommann-Holzboog, 1973.
[11] Shaw P. Using constraint programming and local search methods to solve vehicle routing problems. In: International conference on principles and practice of constraint programming. Pisa, Italy. Berlin, Heidelberg: Springer Berlin Heidelberg; 1998. pp. 417-431.
[12] Potvin JY, Duhamel C, Guertin F. A genetic algorithm for vehicle routing with backhauling. APPL INTELL 1996; 6: 345-355.
[13] Toth P, Vigo D. The granular tabu search and its application to the vehicle-routing problem. INFORMS J COMPUT 2003; 15: 333-346.
[14] Prins C. A GRASP x Evolutionary Local Search Hybrid for the Vehicle Routing Problem. In: Pereira FB,Tavares J, editors. Bio-inspired Algorithms for the Vehicle Routing Problem. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. pp. 35-53.
[15] Mester D, Bräysy O. Active-guided evolution strategies for large-scale capacitated vehicle routing problems. COMPUT OPER RES 2007; 34: 2964-2975.
[16] Pisinger D, Ropke S. A general heuristic for vehicle routing problems. COMPUT OPER RES 2007; 34: 2403-2435.
[17] Zhang Q, Wu X, Liu B, Adiwahono AH, Dung TA, Chang TW. A hierarchical topological planner for multi-storey building navigation. In: 2015 IEEE International Conference on Advanced Intelligent Mechatronics (AIM). Busan, South Korea. New York, NY, USA: IEEE; 2015. pp. 731-736.
[18] Coltin B. Multi-agent pickup and delivery planning with transfers. PhD, Carnegie Mellon University, Pittsburgh, USA, 2014.
[19] Vanclooster A, Ooms K, Viaene P, Fack V, Van de Weghe N, De Maeyer P. Evaluating suitability of the least risk path algorithm to support cognitive wayfinding in indoor spaces: an empirical study. APPL GEOGR 2014; 53: 128-140.
[20] Lin YH, Liu YS, Gao G, Han XG, Lai CY, GU M. The ifc-based path planning for 3d indoor spaces. Adv Eng Inform 2013; 27: 189-205.
[21] Sethian JA. A fast marching level set method for monotonically advancing fronts. P Natl a Sci India A 1996; 93: 1591-1595.
[22] Lourenço HR, Martin OC, Stutzle T. Iterated local search. In: Glover F,Kochenberger G (editors). Handbook of Metaheuristics. Boston, MA, USA: Springer US, 2003. pp. 320-353.
[23] Taillard E, Badeau P, Gendreau M, Guertin F, Potvin JY. A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science 1997; 31: 170-186.
[24] Irnich S, Funke B, Grünert T. Sequential search and its application to vehicle-routing problems. Comput Oper Res 2006; 33: 2405-2429.
[25] Christofides N, Mingozzi A, Toth P. The vehicle routing problem. In: Christofides N, Mingozzi A, Toth P, Sandi L, editors. Combinatorial Optimization. Chichester, UK: Wiley, 1979, pp. 315-338.