|
Article information
2018 , Volume 23, ¹ 5, p.49-62
Dolgova O.E., Peresvetov V.V.
An ant colony optimization algorithm with time relaxed window constraints for solving the vehicle routing problem
The purpose of this paper is to improve the performance of a hybrid method based on ant colony optimization (ACO) that finds approximate solutions of the vehicle routing problem with time windows (VRPTW). In order to solve this problem it is required to design a plan for goods delivery to the customers generating the routes of identical vehicles so that the total travelled distance is minimal. For the VRPTW solving, the hybrid method is developed in which a usage of trial solutions makes it possible to explore the most promising parts of the search space. The initial methods for solution construction, an ant colony optimization (ACO) algorithm and local search are proposed in the framework of the hybrid method. In the ACO algorithm, when generating the routes, it is allowed to violate the time window constraints. A method to restore the feasibility of solutions is implemented within the relaxation scheme under “returns in time” principle. Numerical results for solving all problems with 25, 50 and 100 clients from the Solomon test set are obtained. We provide the results on the time and error of the solution of these problems in comparison with the results of other authors. Some problems and their classes were solved much faster by the algorithm proposed in this paper. Relative deviations from optimal values of the objective function for the most complex tasks decrease with increasing decision time. The proposed approach can be considered to be an additional or an alternative algorithm for solving the cluster type and the long-term planning horizon problems of the VRPTW.
[full text]
Keywords: vehicle routing, time windows, total travelled distance, hybrid algorithm, ant colony optimization, local search
doi: 10.25743/ICT.2018.23.5.005
Author(s):
Dolgova Olga Eduardovna
Position: Junior Research Scientist
Office: Computing center of Far Eastern Branch of the Russian Academy of Sciences
Address: 680000, Russia, Khabarovsk, Kim-Yu-Chena str., 65
Phone Office: (4212)22-72-67
E-mail: o.dolgova@live.ru
SPIN-code: 8693-1032Peresvetov Vladimir Victorovich
PhD.
Position: Senior Research Scientist
Office: Computing center of Far Eastern Branch of the Russian Academy of Sciences
Address: 680000, Russia, Khabarovsk, Kim-Yu-Chena str., 65
Phone Office: (4212)22-72-67
E-mail: peresvv@mail.ru
References:
[1] Desaulniers, G., Madsen, O.B.G., Ropke, S. The vehicle routing problem with time windows . Vehicle Routing: Problems, Methods, and Applications. 2nd Edition / P. Toth, D. Vigo (Eds). SIAM: MOS-SIAM Series on Optimization; 2014: 119–159.
[2] Cordeau, J.-F., Desaulniers, G., Desrosiers, J. VRP with time windows. The Vehicle Routing Problem / P. Toth, D. Vigo (Eds). SIAM: MOS-SIAM Series on Optimization; 2002: 157–193.
[3] Vidal, T., Crainic, T.G., Gendreau, M., Prins, C. Time-window relaxations in vehicle routing heuristics. Journal of Heuristics. 2015; 21(3):329–358.
[4] Khmelev, A.V. A three-phase heuristic for the vehicle fleet and route optimization. Diskretnyi Analiz i Issledovanie Operatsii. 2015; 22(6):55–77. (In Russ.)
[5] Jepsen, M., Petersen, B., Spoorendonk, S., Pisinger, D. Subset-row inequalities applied to the vehicle-routing problem with time windows. Operations Research. 2008; 56(2):497–511.
[6] Baldacci, R., Mingozzi, A., Roberti, R. New route relaxation and pricing strategies for the vehicle routing problem. Operations Research. 2011; 59(5):1269–1283.
[7] Pecin, D., Contardo, C., Desaulniers, G., Uchoa, E. New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS Journal on Computing. 2017; 29(3):489–502.
[8] Slastnikov, S.A. Application of metaheuristic algorithms for the vehicle routing task. Economics and Math. Methods. 2014; 50(1):117–126. (In Russ.)
[9] Baldacci, R., Mingozzi, A., Roberti, R. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research. 2012; (218):1–6.
[10] Kallehauge, B. Formulations and exact algorithms for the vehicle routing problem with time windows. Computers & Operations Res. 2008; (35):2307–2330.
[11] Dorigo, M., Stutzle, T. Ant colony optimization. Cambridge, MA: MIT Press; 2004: 306.
[12] Kazharov, A.A., Kureychik, V.M. Ant colony optimization algorithms for solving transportation problems. Journal of Computer and Systems Sciences International. 2010; 49(1):30–43.
[13] Dolgova, O.E., Peresvetov, V.V. Beam search with ant colony optimization algorithm for solving the vehicle passage problem. Informatika i Sistemy Upravleniya. 2016; 48(2):47–57. (In Russ.)
[14] Dolgova, O.E., Peresvetov, V.V. The vehicle routing problem with time windows. Materialy Vserossiyskoy nauchno-prakticheskoy konferentsii Informatsionnye tekhnologii i vysokoproizvoditel'nye vychisleniya [The vehicle routing problem with time windows. Information Technologies and high performance computations: Proc. All Russian Scientific and Applied Conference]. Khabarovsk; 2013:119–124. (In Russ.)
[15] Dolgova, O.E., Peresvetov, V.V. An ant colony optimization algorithm and local search in solving vehicle routing problems of the cluster type with time windows. Trudy IV Vserossiyskoy nauchno-prakticheskoy konferentsii “Informatsionnye tekhnologii i vysokoproizvoditel'nye vychisleniya” [Information Technologies and high performance computations: Proc. All Russian Scientific and Applied Conference]. Khabarovsk: TOGU; 2017. Ñ. 50–54. (In Russ.)
[16] Nagata, Y., Braysy, O., Dullaert, W. A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Computers and Operations Research. 2010; (37):724–737.
[17] Solomon, M.M. Algorithms for the vehicle routing and scheduling problem with time window constraints. Operations Research. 1987; (35):254–265.
[18] Potvin, J-Y., Rousseau, J-M. An exchange heuristic for routeing problems with time windows. The Journal of the Operational Research Society. 1995; 46:1433–1446.
[19] Kindervater, G.A.P., Savelsbergh, M.W.P. Vehicle routing: handling edge exchanges. Local Search in Combinatorial Optimization / E.H. Aarts, J.K. Lenstra (Eds). Chichester, U.K.: John Wiley & Sons; 1997:311–336.
[20] Shared Facility Center “Data Center of FEB RAS” Available at: http://lits.ccfebras.ru (accessed 08.11.2017) (In Russ.)
[21] Alvarenga, G.B., Mateus, G.R., de Tomi, G. A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows. Computers & Operations Research. 2007; (34):1561–1584.
Bibliography link:
Dolgova O.E., Peresvetov V.V. An ant colony optimization algorithm with time relaxed window constraints for solving the vehicle routing problem // Computational technologies. 2018. V. 23. ¹ 5. P. 49-62
|
