TY - JOUR
T1 - Optimizing the vehicle routing problem with time windows
T2 - A discrete particle swarm optimization approach
AU - Gong, Yue Jiao
AU - Zhang, Jun
AU - Liu, Ou
AU - Huang, Rui Zhang
AU - Chung, Henry Shu Hung
AU - Shi, Yu Hui
N1 - Funding Information:
Manuscript received January 19, 2010; revised November 15, 2010; accepted March 24, 2011. Date of publication May 27, 2011; date of current version February 17, 2012. This work was supported in part by the Project U0835002 of National Natural Science Foundation of China Joint Fund, and in part by National Natural Science Foundation of China under Grant 61070004. This paper was recommended by Associate Editor J. Lazansky.
PY - 2012/3
Y1 - 2012/3
N2 - Vehicle routing problem with time windows (VRPTW) is a well-known NP-hard combinatorial optimization problem that is crucial for transportation and logistics systems. Even though the particle swarm optimization (PSO) algorithm is originally designed to solve continuous optimization problems, in this paper, we propose a set-based PSO to solve the discrete combinatorial optimization problem VRPTW (S-PSO-VRPTW). The general method of the S-PSO-VRPTW is to select an optimal subset out of the universal set by the use of the PSO framework. As the VRPTW can be defined as selecting an optimal subgraph out of the complete graph, the problem can be naturally solved by the proposed algorithm. The proposed S-PSO-VRPTW treats the discrete search space as an arc set of the complete graph that is defined by the nodes in the VRPTW and regards the candidate solution as a subset of arcs. Accordingly, the operators in the algorithm are defined on the set instead of the arithmetic operators in the original PSO algorithm. Besides, the process of position updating in the algorithm is constructive, during which the constraints of the VRPTW are considered and a time-oriented, nearest neighbor heuristic is used. A normalization method is introduced to handle the primary and secondary objectives of the VRPTW. The proposed S-PSO-VRPTW is tested on Solomons benchmarks. Simulation results and comparisons illustrate the effectiveness and efficiency of the algorithm.
AB - Vehicle routing problem with time windows (VRPTW) is a well-known NP-hard combinatorial optimization problem that is crucial for transportation and logistics systems. Even though the particle swarm optimization (PSO) algorithm is originally designed to solve continuous optimization problems, in this paper, we propose a set-based PSO to solve the discrete combinatorial optimization problem VRPTW (S-PSO-VRPTW). The general method of the S-PSO-VRPTW is to select an optimal subset out of the universal set by the use of the PSO framework. As the VRPTW can be defined as selecting an optimal subgraph out of the complete graph, the problem can be naturally solved by the proposed algorithm. The proposed S-PSO-VRPTW treats the discrete search space as an arc set of the complete graph that is defined by the nodes in the VRPTW and regards the candidate solution as a subset of arcs. Accordingly, the operators in the algorithm are defined on the set instead of the arithmetic operators in the original PSO algorithm. Besides, the process of position updating in the algorithm is constructive, during which the constraints of the VRPTW are considered and a time-oriented, nearest neighbor heuristic is used. A normalization method is introduced to handle the primary and secondary objectives of the VRPTW. The proposed S-PSO-VRPTW is tested on Solomons benchmarks. Simulation results and comparisons illustrate the effectiveness and efficiency of the algorithm.
KW - Combinatorial optimization problems (COPs)
KW - set-based particle swarm optimization (S-PSO)
KW - vehicle routing problem with time windows (VRPTW)
UR - http://www.scopus.com/inward/record.url?scp=84857503749&partnerID=8YFLogxK
U2 - 10.1109/TSMCC.2011.2148712
DO - 10.1109/TSMCC.2011.2148712
M3 - Article
AN - SCOPUS:84857503749
SN - 1094-6977
VL - 42
SP - 254
EP - 267
JO - IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews
JF - IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews
IS - 2
M1 - 5773510
ER -