DP-TABU: an algorithm to solve single-depot multi-line vehicle scheduling problem
Tóm tắt
A DP-TABU algorithm is proposed which can effectively solve the multi-line scheduling problem of single Deport (SD-ML-VSP). The multi-line regional coordinated dispatch of the single-line deport of the bus is to solve the problems of idle low-peak vehicles and insufficient peak capacity in single-line scheduling. The capacity of multiple lines at the same station is adjusted to realize resource sharing such as timetables, vehicles, and drivers. Shared capacity such as bus departure intervals and bus schedules. Taking the regional scheduling of multiple lines at the same station as the service object, a vehicle operation planning model based on the objective of optimal public transportation resources (minimum bus and driver costs) is established to optimize the vehicle dispatching mode of multiple lines. We applied this algorithm to the three lines S105, S107, and S159 of Zhengzhou Public Transport Corporation, and the results proved that the algorithm is effective. Through comparison with manual scheduling and simulated annealing algorithm, the advantages of DP-TABU algorithm in performance optimization and robustness are further verified.
Tài liệu tham khảo
Tang Jinjun, Yang Yifan, Qi Yong (2018) A hybrid algorithm for urban transit schedule optimization. Physica A 512:745–755
Yuan W et al (2017) A data-driven and optimal bus scheduling model with time-dependent traffic and demand. IEEE Trans Intell Trans Syst 18(9):2443–2452
Zhao X et al (2020) Two-way Vehicle Scheduling Approach in Public Transit Based on Tabu Search and Dynamic Programming Algorithm. In: 2020 IEEE 5th international conference on intelligent transportation engineering (ICITE). IEEE
Xingquan Z et al (2014) Vehicle scheduling of an urban bus line via an improved multiobjective genetic algorithm. IEEE Trans Intell Trans Syst 16(2):1030–1041
Barbarosoglu Gulay, Ozgur Demet (1999) A tabu search algorithm for the vehicle routing problem. Comput Oper Res 26(3):255–270
Sakoe H, Chiba S (1978) Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans Acoustics Speech Signal Process 26(1):43–49
Consul PC, Jain GC (1973) A generalization of the Poisson distribution. Technometrics 15(4):791–799
Mirjalili S, Siti H, Mohd Z (2010) A new hybrid PSOGSA algorithm for function optimization. In: 2010 international conference on computer and information application. IEEE
Enjian Yao et al (2020) Optimization of electric vehicle scheduling with multiple vehicle types in public transport. Sustainable Cities Soc 52:101862
Min W et al (2016) An adaptive large neighborhood search heuristic for the electric vehicle scheduling problem. Comput Oper Res 76:73–83
Murray JJ et al (2002) Adaptive dynamic programming. In: IEEE transactions on systems, man, and cybernetics, Part C (Applications and Reviews) 32(2), 140-153
Eddy Sean R (2004) What is dynamic programming? Nat Biotechnol 22(7):909–910
Olle S, Guzzella L (2009) A generic dynamic programming Matlab function. In: 2009 IEEE control applications,(CCA) & intelligent control, (ISIC). IEEE
Fiechter C-N (1994) A parallel tabu search algorithm for large traveling salesman problems. Discrete Applied Mathematics 51(3):243–267
Costa D (1994) A tabu search algorithm for computing an operational timetable. Euro J Oper Res 76(1):98–110
Schermer Daniel, Moeini Mahdi, Wendt Oliver (2019) A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations. Comput Oper Res 109:134–158
Osman Ibrahim H, Kelly James P (1997) Meta-heuristics theory and applications. J Oper Res Soc 48(6):657–657
Voß S et al (2012) eds. Meta-heuristics: advances and trends in local search paradigms for optimization. Springer Science & Business Media
Jones Dylan F, Mirrazavi S. Keyvan, Tamiz Mehrdad (2002) Multi-objective meta-heuristics: an overview of the current state-of-the-art. Euro J Oper Res 137(1):1–9
Beyers JM et al (2003) Neighborhood structure, parenting processes, and the development of youths externalizing behaviors: a multilevel analysis. Am J Community Psychol 31(1):35–53
Zhang CY et al (2007) A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Comput Oper Res 34(11):3229–3242
Li Jun-Qing et al (2011) A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem. Int J Adv Manuf Technol 52(5):683–697