| 引用本文: | 陈希琼,胡大伟,王宁.多目标同时取送货选址–路径问题的多起点变邻域搜索算法[J].控制理论与应用,2022,39(7):1229~1241.[点击复制] |
| CHEN Xi-qiong,HU Da-wei,WANG Ning.A multi-start variable neighborhood search for multi-objective location routing problem with simultaneous pickup and delivery[J].Control Theory and Technology,2022,39(7):1229~1241.[点击复制] |
|
| 多目标同时取送货选址–路径问题的多起点变邻域搜索算法 |
| A multi-start variable neighborhood search for multi-objective location routing problem with simultaneous pickup and delivery |
| 摘要点击 1175 全文点击 394 投稿时间：2021-03-30 修订日期：2022-07-01 |
| 查看全文 查看/发表评论 下载PDF阅读器 |
| DOI编号 10.7641/CTA.2022.10265 |
| 2022,39(7):1229-1241 |
| 中文关键词 综合交通运输 多起点变邻域搜索 多蚁群算法 同时取送货选址路径 多目标局部搜索 |
| 英文关键词 comprehensive transportation multi-start variable neighborhood search multiple ant colony algorithm location routing problem with simultaneous pickup and delivery multi-objective local search |
| 基金项目 国家自然科学基金项目(71971030), 陕西省自然科学基金重点项目(2021JZ–20), 中央高校基本科研业务费专项(300102220102, 300102229304), 陕西省教育厅专项科研基金项目(17JK0284)资助 |
|
| 中文摘要 |
| 为使同时取送货的选址–路径问题(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. |
|
|
|
|
|