同时收发运输路径问题的禁忌搜索算法

研究同时收发的运输路径问题,要求运输工具到每个客户收取和发送一次完成,并且在运输工具容量的限制下,寻求每个运输工具的运输路径,使总运费为最少.提出两阶段的求解过程:先用启发式算法得到初始解,然后用层次禁忌搜索算法得到改进解.计算实验表明,同样规模的问题,算法所需时间比直接使用禁忌搜索算法要少.

Tabu Search for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery Service

In this paper we study the vehicle routing problem with simultaneous pick-up and delivery (VRPSPD). A vehicle can pick up and deliver the entire amount of a commodity available or required at a customer. A route is a circuit over some customers, starting and finishing at the depot. The VRPSPD consists of constructing at most K vehicle routes such that all pickup and delivery requests are satisfied, the load of a vehicle never exceeds its capacity and the sum of route costs is minimized. Two-phase algorithm, a heuristic to get an initiate and two-layered tabu search to obtain an improved solution, is presented. From computational experiments this algorithm is more effective than a simple tabu search algorithm.