A distributed VNS algorithm for optimizing dial-a-ride problems in large-scale scenarios |
| |
| Institution: | 1. Center for Biomedical Technology, Universidad Politécnica de Madrid, Spain;2. Facultad de Informática, Universidad Politécnica de Madrid, Spain;1. Intelligent Transportation Systems Laboratory, Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA 0219, USA;2. Singapore-MIT Alliance for Research and Technology, 1 CREATE Way, #09-02 CREATE Tower, Singapore 138602, Singapore;3. Edmund K. Turner Professor of Department of Civil and Environmental Engineering, MIT. Room 1-181, 77 Massachusetts Avenue, Cambridge, MA 02139, USA;4. Institute of Transportation Engineering, Department of Civil Engineering, Tsinghua University, Beijing 100084, China;1. Warsaw University of Technology, Faculty of Transport, ul. Koszykowa 75, 00-662 Warszawa, Poland;2. Upper Silesian Aviation Group, al. Korfantego 38, 40-161 Katowice, Poland;1. Department of Industrial Engineering and Innovation Sciences, Eindhoven University of Technology, Eindhoven, The Netherlands;2. Department of Computer Science, VU University Amsterdam, Amsterdam, The Netherlands;3. Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands;1. Goiás Federal Institute of Education, Science and Technology, Rua Maria Vieira Cunha, 775, Residencial Flamboyant, 75804-714 Jataí, GO, Brazil;2. São Paulo State University, Avenida Brasil 56, Centro, PO Box 31, 15385-000 Ilha Solteira, SP, Brazil;1. International Center of Management Science and Engineering, School of Management and Engineering, Nanjing University, Nanjing 210093, PR China;2. Department of Management Sciences, City University of Hong Kong, Tat Chee Ave, Kowloon Tong, Hong Kong;3. School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore |
| |
| Abstract: | These days, transportation and logistic problems in large cities are demanding smarter transportation services that provide flexibility and adaptability. A possible solution to this arising problem is to compute the best routes for each new scenario. In this problem, known in the literature as the dial-a-ride problem, a number of passengers are transported between pickup and delivery locations trying to minimize the routing costs while respecting a set of prespecified constraints. This problem has been solved in the literature with several approaches from small to medium sized problems. However, few efforts have dealt with large scale problems very common in massive scenarios (big cities or highly-populated regions). In this study, a new distributed algorithm based on the partition of the requests space and the combination of the routes is presented and tested on a set of 24 different scenarios of a large-scale problem (up to 16,000 requests or 32,000 locations) in the city of San Francisco. The results show that, not only the distributed algorithm is able to solve large problem instances that the corresponding sequential algorithm is unable to solve in a reasonable time, but also to have an average improvement of 9% in the smaller problems. The results have been validated by means of statistical procedures proving that the distributed algorithm can be an effective way to solve high dimensional dial-a-ride problems. |
| |
| Keywords: | Variable neighborhood search Dial-a-ride problem Transportation Demand-responsive transport Distributed algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
