Neural-like encoding particle swarm optimization for periodic vehicle routing problems

• Published in: Expert systems with applications 2019-12, Vol.138, p.112833, Article 112833
• Main Authors: Chen, Ruey-Maw, Shen, Yin-Mou, Hong, Wei-Zhi
• Format: Article
• Language: English
• Subjects: Algorithms; Alternative depot savings algorithm; Customer services; Logistics; Neural-like discrete PSO; Optimization; Particle swarm optimization; Periodic vehicle routing problem; Route planning; Routing; Schedules; Scheduling; Search process; Vehicle routing
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2019.112833

•Discrete PSO algorithm is used to solve customer service mode problem.•Neural-like discrete PSO algorithm is used to solve vehicle routing problem.•Heuristics are proposed to improve search performance of both algorithms.•Alternative depot savings algorithm is proposed to reduce route crossing problem.•Local search mechanism additionally employed to improve solution quality. The periodic vehicle routing problem (PVRP) is an important problem in the logistics field and involves finding the solutions to two sub-problems, namely (1) determining the optimal customer service mode; and (2) establishing the optimal vehicle routing schedule in accordance with the pre-determined customer service mode. However, existing solutions for the PVRP consider only the vehicle routing problem. In other words, they simply assume that the optimal customer service mode is known in advance. Accordingly, the present study proposes a dual particle swarm optimization (PSO) framework for solving both sub-problems simultaneously. In particular, a discrete PSO (DPSO) algorithm is applied on the first level, in the outer layer, to establish the optimal service mode for each customer, and a neural-like DPSO (NDPSO) is then applied in the inner layer to determine (1) the optimal assignment of the depot vehicles to the customers which are to be serviced each day based on the customer service mode established in the outer layer (i.e., the “customer-vehicle correspondence” problem), and (2) the sequence of customer visits to be paid by each vehicle each day (i.e., the “optimal vehicle routing” problem). For both PSOs, a sweep heuristic is applied to generate diverse initial solutions for the particle search process. In addition, an alternative depot savings algorithm is proposed to avoid the route crossing phenomenon inherent in conventional vehicle routing algorithms. The performance of the inner layer NDPSO is evaluated by comparing the solutions for six common PVRPs with the best known solutions (BKS) presented in the literature given a prior knowledge of the optimal customer service mode in every case. The performance of the NDPSO is further investigated with and without the alternative depot savings algorithm and with and without the use of a local search mechanism to enhance the quality of the PSO solutions, respectively. Finally, the feasibility of the full DPSO and NDPSO framework is confirmed by comparing the PVRP solutions with the BKS reported in previous studies. In general, th