A Parallel Simulated Annealing Algorithm for the Optimization TDVRP

Shanshan Cui; Zhao Jing; Bin Shi

doi:10.47297/taposatWSP2633-456901.20250604

PDF
Export
Share
Collection
Album

A Parallel Simulated Annealing Algorithm for the Optimization TDVRP

Volume 6, Issue 4

Views: 0 Downloads: 3

A Parallel Simulated Annealing Algorithm for the Optimization TDVRP
A Parallel Simulated Annealing Algorithm for the Optimization TDVRP
1.School of Information and Computer Engineering, Chuzhou Vocational and Technical College, 239000, China
2.China Railway Fourth Bureau, 230000, China
Vol. 6, Issue 4, Pages: 5-10(2025)
Published：22 April 2025
DOI：10.47297/taposatWSP2633-456901.20250604
Accepted：

Scan QR Code

Cui Shanshan,Jing Zhao,Shi Bin.A Parallel Simulated Annealing Algorithm for the Optimization TDVRP[J].Theory and Practice of Science and Technology,2025,06(04):5-10.
DOI：

Cui Shanshan,Jing Zhao,Shi Bin.A Parallel Simulated Annealing Algorithm for the Optimization TDVRP[J].Theory and Practice of Science and Technology,2025,06(04):5-10. DOI： 10.47297/taposatWSP2633-456901.20250604.

摘要

Abstract

In this paper

parallel algorithm based on muti-core cell processors for solving time-dependent vehicle routing problems has been proposed. The aim is to optimize algorithm performance to a greater extent. The SA algorithm has achieved big data parallelism and improved speed. However

the efficiency of this implementation is still limited

as traditional SA algorithms still run at low parallelism on new platforms and computational resources can not be fully utilized. For these problems

This algorithm creates the initial solution using heuristics

and two editions of parallel algorithm are described

which referred to as independent search and collaborative search. Figliozzi's benchmark test covered the calculation results of 56 test questions from 100 customers

the results show that (i) compared with traditional sequential SA

p-SA gains better solutions in different time dependent speeds with an accepted computational time. Hence

through data analysis

P-SA can effectively solve the TDVRP problem

and can be extended to deal with other variants of the open vehicle routing problem and other combinatorial optimization problems.In addition

the proposed algorithm can significantly improve the execution efficiency of simulated annealing processes.

关键词

Keywords

references

Li Jing Tan,Fu Yong Lin,Hong Wang . BFO Optimization Algorithms for Vehicle Routing Problem with Time Windows[J]. Applied Mechanics & Materials, 2014, 543-547:1884-1887.

Battarra M, Monaci M, Vigo D. An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem. Comput Oper Res 2009;36(11):3041–50.

Prins C. A simple and effective evolutionary algorithm for the vehicle routing problem. Comput Oper Res 2004;31(12):1985–2002.

Vidal T, Crainic TG, Gendreau M, Prins C. A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time windows. Comput Oper Res 2013;40(1):475–89.

Yusuf, Ismail. Applied genetic algorithm for solving rich VRP [J].Applied Artificial Intelligence, 2014: 957-991.

Nagata Y, Bräysy O, Dullaert W. A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Comput OperRes 2010;37(4):724–37.

Onbas ¸o˘ glu, E. Parallel simulated annealing algorithms in global optimization [J]. Journal of Global Optimization, 2001: 27–50.

Czech, Z.J., Co-operation of processes in parallel simulated annealing, Proc. of the 18th IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2007), (November 13-15, 2006), Dallas, Texas, USA.

Tlili T , Krichen S . A simulated annealing-based recommender system for solving the tourist trip design problem[J]. Expert Systems with Application, 2021(Dec.):186.

Moghaddam R.T. A hybrid simulated annealing for capacitated vehicle routing problems with the dependent route length [J]. Applied Mathematics and Computation, 2006, 176: 445-454.

He, Guo-Xian. Application of annealing algorithm based on random simulated solution in distribution VRP for single logistics center [J]. Journal of the China Railway Society, 2009: 92-97.

Da-Wei Zhu, Zhi Qiang. Simulated annealing algorithm for vehicle routing problem [J]. China Journal of Highway and Transport, 2006:123-126.

Majid Soheili, Amir Masoud Eftekhari-Moghadam DQPFS: Distributed quadratic programming based feature selection for big data[J] Journal of Parallel and Distributed Computing, 2020, 138(C).

Alazzam, Hadeel, AbuAlghanam, Orieb, Sharieh, Ahmad Best path in mountain environment based on parallel A* algorithm and Apache Spark[J] The Journal of Supercomputing, 2021(prepublish).

Shi S M , Wang X F , Zhong F . The research of typical control strategy of electronic power transformer in parallel operation[C]// 2016 IEEE Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC). IEEE, 2016.

Blocho M , Nalepa J . A Parallel Algorithm for Minimizing the Fleet Size in the Pickup and Delivery Problem with Time Windows[C]// European Mpi Users Group Meeting. 2015.

Alert me when the article has been cited

Submit

No data

Related Author

No data

Related Institution

No data

⁰