多目标同时取送货选址–路径问题的多起点变邻域搜索算法

A multi-start variable neighborhood search for multi-objective location routing problem with simultaneous pickup and delivery

中文关键词  综合交通运输  多起点变邻域搜索  多蚁群算法  同时取送货选址路径  多目标局部搜索

英文关键词  comprehensive transportation  multi-start variable neighborhood search  multiple ant colony algorithm  location routing problem with simultaneous pickup and delivery  multi-objective local search

中文摘要

      为使同时取送货的选址–路径问题(LRPSPD)的总成本和各路径间最大长度差最小化, 建立同时考虑车辆 容量和行驶里程约束的LRPSPD双目标模型. 采用多蚁群算法构造多个以信息素为关联的初始解, 作为多目标变邻 域搜索算法搜索的多个起点, 构造四类邻域结构进行变邻域搜索, 并根据最新获得的最优邻域解更新蚂蚁信息素, 从而使蚁群算法产生的多个初始解间、以及初始解与变邻域搜索产生的解之间均存在正向影响关系. 用该算法求 得文献中4组共128个算例的近似Pareto解集, 结果证明了最小化路径间最大长度差目标对于节点及需求分布不集 中算例的重要意义. 以绝对偏向最小化总成本的解与文献中仅最小化总成本的几种算法的算例结果进行比较, 结果 表明算法可在极短的运行时间里求得权衡各目标的Pareto解, 并使最小总成本目标值具有竞争性.

英文摘要

      In order to minimize the total cost and maximum gap among each tour in a location-routing problem with simultaneous pickup and delivery (LRPSPD), a LRPSPD bi-objective model, which considers the vehicle capacity and travel distance constrains simultaneously, is established. Multiple ant colonies are used to construct the initial solutions. The initial solutions are associated with each other by multiple pheromones and are taken as multi-starts of bi-objective variable neighborhood search algorithm. Four types of neighborhood structures are established for the variable neighborhood search. The pheromones are updated according to the latest optimal neighborhood solutions, so that there are positive influence relationships not only among multiple initial solutions generated by ants, but also between initial solutions and solutions generated by variable neighborhood search. The proposed multi-start variable neighborhood search (MSVNS) approach is then used to solve 128 instances, which are classified in 4 sets in the literature and obtain the approximate Pareto solutions. The results demonstrate the significance of considering the maximum gap among each tour as a minimized objective in some instances, which have scattered nodes and demands distribution. Compare the solutions with lowest cost (absolute preference to minimize the costs) from Pareto solutions with previous results from literature which minimize the total costs only. The comparison results indicate that the procedure can be operated in extremely short running time and the Pareto solutions acquired by the algorithm provide good tradeoff between two objectives and yield a competitive solution of the cost-minimizing objective.