Cuckoo search and enhanced artificial bee colony heuristic methods for vehicle routing problem with backhaul and time window constraints

The vehicle routing problem with backhauls and time windows (VRPBTW) aims to find a feasible vehicle route that minimizes the total traveling distance while imposing capacity, backhaul, and time-window constraints. In this dissertation, a mathematical model of VRPBTW is introduced to obtain an optimal solution. The heuristics, namely the nearest urgent candidate (NUC), which applies the urgency priority and candidate techniques, and the nearest neighbor with roulette wheel selection (NNRW) which is a combination of a roulette wheel selection method and the improved nearest neighbor heuristic, are also presented to solve this problem. Moreover, two metaheuristic methods are presented to obtain the optimal or near optimal solutions. The first is a cuckoo search (CS) algorithm, which is applied to this problem for the first time. The second is the enhanced artificial bee colony (EABC) algorithm which uses a forbidden list, the sequential search for onlookers, and the combination of neighborhood search techniques. The computational results indicate that proposed algorithms yield good performance in terms of solution quality, especially EABC. It obtained 33 ties or new best known solutions out of 45 instances comparing with the best known solutions found in the literature. Hence, the proposed algorithms are the effective ways to solve the VRPBTW.

带回程配送与时间窗的车辆路径问题（Vehicle Routing Problem with Backhauls and Time Windows, VRPBTW）旨在在满足车辆容量约束、回程配送要求以及时间窗约束的条件下，寻找到总行驶距离最小的可行车辆路径方案。本论文首先构建了VRPBTW的数学模型以求解其最优解。
本文还提出了两类启发式算法用于求解该问题：一是基于紧急度优先级与候选集策略的最近紧急候选（Nearest Urgent Candidate, NUC）算法；二是融合轮盘赌选择方法与改进型最近邻启发式的轮盘赌选择最近邻（Nearest Neighbor with Roulette Wheel Selection, NNRW）算法。
此外，本文提出两种元启发式算法以获取该问题的最优或近似最优解：第一种为布谷鸟搜索（Cuckoo Search, CS）算法，该算法首次被应用于VRPBTW的求解；第二种为改进型人工蜂群（Enhanced Artificial Bee Colony, EABC）算法，该算法引入了禁忌列表、旁观蜂顺序搜索策略以及邻域搜索技术的融合机制。
计算实验结果表明，本文所提出的算法在解质量方面均表现优异，其中EABC算法的性能尤为突出。在45个测试算例中，相较于现有文献中的已知最优解，EABC算法共取得33个持平解或新的已知最优解。综上，本文提出的算法均为求解VRPBTW的有效方法。