求解配送\收集旅行商问题的遗传算法

Genetic algorithm solving salesman problem with pickup and delivery

配送 \收集旅行商问题 (TSPD)是物流学中的一个重要问题 ,但与一般的旅行商问题 (TSP)相比 ,人们对该问题的研究有限 ,而且大多假定必须在完成所有的配送需求后才服务收集需求。本文放松这一约束条件 ,结合最邻近启发式和k -opt局域搜索策略 ,设计了一种求解TSPD的遗传算法 ,计算结果表明 ,该算法性能优良 ,计算效率较高。

Traveling Salesman Problem with Pickup and Delivery (TSPD) is an important problem in logistics. However, much less effort, in which authors often assume that pickups are served after all deliveries, has been devoted to the study of TSPD as compared to the classical Traveling Salesman Problem (TSP). In this paper, the assumption is eliminated, and a particular genetic algorithm is applied to solve the problem in combination with the nearest heuristic method and local search strategy. The results show that the algorithm possesses superior properties and rather high efficiency.