带约束k-means结合贪心法求解多车型软时间窗集油车辆调度问题
刘逗逗 , 王文发 , 许淳
延安大学学报(自然科学版) ›› 2026, Vol. 45 ›› Issue (3) : 113 -119.
带约束k-means结合贪心法求解多车型软时间窗集油车辆调度问题
Constrained k-means combined with greedy algorithm for solving the multi-vehicle type soft time window oil collection vehicle routing problem
针对车辆路径问题(VRP)的现有算法在解决采油厂带时间窗多车型多费用集油车辆调度时存在的不足,提出一种带约束k-means结合贪心法的分阶段多目标混合算法。综合考虑构成集油运输费用的各项指标,建立混合整数规划模型;应用贪心法结合车辆载重约束将油井集进行划分,得到聚类的初始子簇和集油所需车辆数;定义多因素加权组合距离,应用带约束k-means算法,通过“约束优先+费用最小化”的双目标迭代,将油井集划分为子簇;在油井子簇内,采用贪心法优化车辆集油的行驶路径;通过簇划分、路径优化及全局调优的两个阶段和三层策略,在满足约束的前提下,使集油车辆数和总费用最小化。该算法在某采油厂集油业务中的应用表明,日集油井次下降约18.28%,显著提高了生产效率和经济效益。
Aiming at the deficiencies of existing Vehicle Routing Problem (VRP) algorithms in addressing the oil-gathering vehicle scheduling problem with time windows, multiple vehicle types and multi-dimensional costs in oil production plants, a phased multi-objective hybrid algorithm combining constrained k-means and the greedy algorithm is proposed. A mixed integer programming model is established by comprehensively considering all indicators that constitute the oil-gathering transportation cost. The greedy algorithm integrated with vehicle load constraints is applied to partition the set of oil wells to obtain the initial clustering sub-clusters and the number of vehicles required for oil gathering. A multi-factor weighted composite distance is defined and the constrained k-means algorithm is adopted to divide the oil well set into sub-clusters through dual-objective iteration following the principle of “constraint priority + cost minimization”, the greedy algorithm is employed to optimize the driving routes of oil-gathering vehicles within each oil well sub-cluster, and based on the two-stage and three-layer strategy encompassing cluster partitioning, route optimization and global refinement, the number of oil-gathering vehicles and the total cost are minimized on the premise of satisfying all constraints. The application of this algorithm in the oil-gathering business of a certain oil production plant shows that the daily number of oil well visits has decreased by nearly 18.28%, which significantly improves production efficiency and economic benefits.
| [1] |
轩苗苗. 基于改进遗传算法的冷链物流配送路径优化研究[D]. 淮南:安徽理工大学,2025. |
| [2] |
丘凯. 深度强化学习在车辆路径问题中的应用研究[D]. 广州:广东财经大学,2025. |
| [3] |
李二超,张智钊. 在线动态订单需求车辆路径规划[J]. 山东大学学报(工学版),2024,54(5):62-73. |
| [4] |
刘狄. 考虑碳排放和服务水平的多中心配送路径优化研究[D]. 重庆:重庆交通大学,2025. |
| [5] |
|
| [6] |
|
| [7] |
|
| [8] |
|
| [9] |
张冬梅,李敏,徐大川, |
| [10] |
赵雄,李琳. 基于聚类的LNS算法求解异构VRP问题[J]. 计算机技术与发展,2023,33(9):98-104. |
| [11] |
朱珠,温召成,臧洁. 电子商务快递末端配送模式优化研究[J]. 武汉理工大学学报(交通科学与工程版),2024,46(1):139-145. |
| [12] |
宋虹颖. 考虑多车型的成品油主动配送规划方法研究[D]. 长春:吉林大学,2025. |
| [13] |
戴永寿,李韶光,李立刚 |
| [14] |
张雪婷. 基于K-Means++和遗传算法的提货车辆路径研究[D]. 北京:首都经济贸易大学,2017. |
| [15] |
梁学恒,杨家其,向子权. 两阶段BSO-SA算法求解带单边软时间窗的多车型VRP问题[J]. 武汉理工大学学报(交通科学与工程版),2024,48(1):19-24. |
| [16] |
罗蒙,高超,王震. 基于带约束谱聚类的启发式车辆路径规划算法优化方法[J]. 计算机应用,2025,45(5):1387-1394. |
| [17] |
蔡祥. 带时间窗的同时取送货车辆路径问题优化模型及算法研究[D]. 南昌:南昌大学,2023. |
| [18] |
李敏,倪少权,周凌. 基于订单邻域的成品油二次配送中带时间窗车辆路径规划问题[J]. 计算机集成制造系统,2015,21(8):2158-2169. |
国家自然科学基金项目(72461032)
陕西省自然科学基础研究计划项目(2023-JC-QN-0744)
/
| 〈 |
|
〉 |