同时集散货物的开放式车辆路径问题研究

本文研究了车辆工作时间限制下同时集散货物的多配送中心开放式车辆路径问题,以车辆数和运输里程最小为目标,建立了多目标规划模型,提出了基于拉格朗日松弛技术和禁忌搜索算法的混合求解算法。 该算法首先求出最优解的最大下界,然后采用客户点的分配和调整策略实现解的可行化,其中禁忌搜索引入了4种领域搜索方法,采用了随机变领域搜索方法和重起策略。算例分析表明,该算法能有效地找到满意解,且采用开放式安排路线比闭合式安排路线更加经济合理。

Research on the Open Vehicle Routing Problemof with Simultaneous Deliveries and Pickups

Open vehicle routing problem of multiple distribution centers with simultaneous deliveries and pickups is studied, in which the number and working time of the vehicles are limited. Based on the minimum number and travel distance of vehicles, a multi-objective model is proposed. A novel mixed algorithm based on lagrangian relaxation technique and tabu search algorithm is given, which obtains the maximum lower bound of the optimal solution and then adopts the strategy of assignment and adjustment for clients to achieve the feasible solution. For the tabu search algorithm, a random neighborhood ordering and perturbation mechanisms based on four neighborhood search methods are employed. Computational results show that this algorithm is effective to search the satisfactory solutions and the open collaborative arrangement of vehicle routing is more economic and reasonable than the close independent arrangement of vehicle routing.