带约束k-means结合贪心法求解多车型软时间窗集油车辆调度问题

刘逗逗 ,  王文发 ,  许淳

延安大学学报(自然科学版) ›› 2026, Vol. 45 ›› Issue (3) : 113 -119.

PDF (658KB)
延安大学学报(自然科学版) ›› 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

Author information +
文章历史 +
PDF (672K)

摘要

针对车辆路径问题(VRP)的现有算法在解决采油厂带时间窗多车型多费用集油车辆调度时存在的不足,提出一种带约束k-means结合贪心法的分阶段多目标混合算法。综合考虑构成集油运输费用的各项指标,建立混合整数规划模型;应用贪心法结合车辆载重约束将油井集进行划分,得到聚类的初始子簇和集油所需车辆数;定义多因素加权组合距离,应用带约束k-means算法,通过“约束优先+费用最小化”的双目标迭代,将油井集划分为子簇;在油井子簇内,采用贪心法优化车辆集油的行驶路径;通过簇划分、路径优化及全局调优的两个阶段和三层策略,在满足约束的前提下,使集油车辆数和总费用最小化。该算法在某采油厂集油业务中的应用表明,日集油井次下降约18.28%,显著提高了生产效率和经济效益。

Abstract

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.

Graphical abstract

关键词

聚类分析 / k-means算法 / 贪心法 / 车辆路径问题(VRP) / 整数规划模型

Key words

clustering analysis / k-means algorithm / greedy algorithm / VRP / integer programming model

引用本文

引用格式 ▾
刘逗逗,王文发,许淳. 带约束k-means结合贪心法求解多车型软时间窗集油车辆调度问题[J]. 延安大学学报(自然科学版), 2026, 45(3): 113-119 DOI:

登录浏览全文

4963

注册一个新账户 忘记密码

采油厂集油业务是将采油厂各分散油井产出的原油通过各种方式汇集并输送到集输站(如集油点、联合站和接转站等)的过程,是石油企业油气集输的核心环节。高原山区油田的油井分散在沟谷山梁间,集油主要采用车辆运输方式,其业务技术核心是集油车辆的调度与路径优化。针对车辆调度与路径优化问题,国内外学者已提出了多种改进策略和算法[1-8]。聚类作为无监督学习的核心算法之一,以其基于相似度/距离度量将数据集样本进行划分的本质,在很多领域被广泛研究和应用[9]。k-means算法采用“聚类分组、路径优化”的两阶段策略,成为求解VRP问题的重要方法[10-14]。其中,带约束k-means算法通过降低问题规模、优化初始解,在满足约束条件的前提下,实现所有车辆的总行驶成本最小化[15-18]。采油厂集油车辆的调度与路径优化问题,由于构成运输成本的因素非常多,现有关于VRP问题的算法不完全适用该问题的求解,同时,现有算法也未考虑不同载重行驶费用的变化,且完成集油任务需要的车辆数大多给出预估值,未精准确定。本文针对多车型多费用软时间窗不确定车辆数非满载集油车辆的调度和路径优化问题,提出一种带约束k-means结合贪心法的分阶段多目标混合算法。该方法综合考虑构成集油运输费用的各项指标,建立多目标决策模型,通过“约束优先+费用最小化”的双目标迭代,在满足约束的前提下,通过簇划分、路径优化、全局调优的两阶段三层策略,使集油车辆数和总费用最小化。

1 问题描述

采油厂车辆运输集油问题描述如下:采油厂拥有若干口油井、一个集油点和一个车场,车场有不同车型的车辆若干,当天部分油井需要车辆运输方式集油。设计完成当天集油任务的车辆调度方案,确定各车型发车数及各车辆集油的行驶路线,使总成本最少。

1.1 涉及因素

1)集油点、车场和所有油井及其之间的道路与长度构成的网;2)车型及其数量、各车型关于行驶长度及载重的油耗率;3)车型车辆的固定费用和行驶费用;4)油井储油罐容量;5)当天需要集油油井储油罐的存油量。

1.2 问题假定

1)单车场、单集油点;2)所有车型车辆的运载能力能够保证当天集油任务的完成;3)每个油井储油罐,一定存在一种车型,其最大载重不小于该油井储油罐的存油量。

1.3 问题约束

1) 每个油井的集油任务都有完成时间限制,且由一辆车完成。

2) 每辆车完成集油任务总时间:行驶时间+油井集油时间+集油点卸油时间。

3) 集油车辆的行驶路线均为:从车场出发到分散分布的油井集油,然后到集油点卸油,最后返回车场。

2 集油车辆调度与路径优化问题的数学模型

2.1 符号定义

2.2 决策变量定义

yium=1,油井i由m型车的第u辆集油,0,否则,i=1,2,⋯,N-1, m=1,2,⋯,M,u=1,2,⋯,um;
xijum=1,第u辆m型车油井i集油后到油井j集油,0,否则,i,j=1,2,⋯,N-1, m=1,2,⋯,M,u=1,2,⋯,um。

2.3 数学模型

集油车辆到达油井j的时间tj通过公式(1)递推计算:

t0=0,                                                    tj=∑i=0N∑m=1M∑u=1um(ti+ttij+gti)×xijum,j=1,2,⋯,N-1。

集油车辆到达油井j(j=1,2,⋯,N-1)开始集油时间tj,需满足油井j的集油时间窗约束,即ETj≤tj≤LTj。否则,集油时间早于ETi,存油量不足,导致集油成本增加,产生惩罚成本;集油时间晚于LTi,可能出现油井储油罐溢出事故,造成原油流失浪费和环境污染,产生损失成本。

第u辆m型车按油井编号顺序完成油井i的集油决策后的总载重通过式(2)计算:

w0um=0,wium=∑j=1i∆jm×gj×yjum,i=1,2,⋯,N-1,m=1,⋯,M, u=1,⋯,um。

综上所述,带时间窗的多车型多费用不确定车辆数非满载集油问题的数学模型如下:

min Z=∑i=0N∑j=0N∑m=1M∑u=1umcijmwium×xijum-∑j=1N-1Tj×scj+∑j=1N-1Tj×dcj;
s.t.∑m=1M∑u=1umΔim×yium=1, i=1,2,⋯,N-1;
∑i=0N-1xijum=yjum, j=1,2,⋯,N-1, ∀m,u;
∑j=0N-1xijum=yium, i=1,2,⋯,N-1, ∀m,u;
∑i=1N-1∆im×gi×yium=wN-1um≤qm, ∀m,u;
∑j=1N-1x0jum=1, ∀m,u;
∑i=0N-1xihum=∑j=0N-1xhjum=1, h=1,⋯,N-1,∀m,u;
∑i=0N-1xiNum=1, ∀m,u;
xN0um=1, ∀m,u;
xijum=1或0,i=0时,j≠N,i=N时,j=0,i,j=0,1,2,⋯,N,∀m,u;
yium=1或0,i=1,2,⋯,N-1,∀m,u。

目标函数(3)综合考虑集油车辆的固定费用、行驶费用、时间惩罚成本。约束(4)保证每一口油井只有一种相容车型的一辆车进行集油,约束(5)、(6)表示两决策变量之间的约束关系,约束(7)表示每辆车的集油总量wN-1um不超过该车的载重上限,约束(8)、(9)、(10)、(11)表示每辆车从车场出发,完成集油任务,到集油点交付原油,最后回到车场,约束(12)、(13)为对相应决策变量的约束。

本文设计了带约束k-means结合贪心策略的混合求解算法,实现车辆调度和行驶路径的同步优化。

3 带约束k-means结合贪心策略的算法设计

应用贪心法结合车辆载重约束将油井集划分为互不相交的K个子集,得到聚类的K个子簇,每个子簇对应1辆载重相容集油车;定义“多因素加权组合距离”,应用改进的带约束k-means算法,通过“约束优先+费用最小化”的双目标迭代,将油井集划分为K个子簇;应用贪心法优化集油车辆在对应子簇的行驶路径;通过簇划分、簇中心更新和簇内路径优化的两个阶段三层策略,最小化集油总费用,得到数学模型满足约束条件、满足精度的近似最优解。算法流程图见图1。

3.1 基于贪心法的油井初始簇划分

当天需要集油油井N-1口,油井i的存油量为gi(i=1,⋯,N-1),总存油量G=∑i=1N-1gi。车场车辆总数为U=∑m=1Mum,车辆总运力为Q=∑m=1Mum×qm。

1)定义N-1×(N-1)阶对称矩阵DN-1×(N-1)=(dij)N-1×(N-1)表示N-1口油井相互之间的距离。

2)将每口油井i(i=1,⋯,N-1)的信息定义为结点tnodei=(i,sgi),构造以结点tnodei=(i,sgi)为根结点的树Ti, i为树Ti的编号,sgi为树Ti上所有叶子结点存油量的和。

3)创建N-1棵树的森林FT={T1,T2,⋯,TN-1}。

4)定义森林FT中两棵树Tn和Tm的距离TDnm=mindiji,sgi∈Tn且是叶子结点,同时j,sgj∈Tm且是叶子结点。

5)选择当前森林FT中使距离TDnm最小的两棵树Th和Tl(h<l)。

6)如果sgh+sgl≤qM,将两棵树Th和Tl合并为一棵树,同时从森林FT中删除树Th和Tl;将合并的新树命名为Th,加入森林FT中,令sgh=sgh+sgl,则Th的根结点为(h,sgh);然后继续步骤5)、步骤6);否则,如果sgh+sgl>qM,按照TDnm 值从小到大的次序,逐次选择对应的两颗树Th 和Tl (h<l),继续步骤6)。

7)直到FT中任意两颗树Th 和Tl,都有sgh +sgl >qM,结束森林FT中树的合并操作,最终森林FT中有K颗树。

8)当前森林FT中每一棵树的叶子结点的编号构成了油井集SS的一个子集,所有子集互不相交。因此,森林FT中的K颗树将油井集SS划分为K个簇SS={SS1,SS2,⋯,SSK},K就是k-means聚类的簇数,SS={SS1,SS2,⋯,SSK}是油井集的初始簇划分,|SSk|=snk(k=1,2,⋯,K)。

9)对SS={SS1,SS2,⋯,SSK}的每个簇指派一辆载重相容的车辆集油,所以,K也是完成当天集油任务需要调度的车辆数。

10)若SSk(k=1,2,⋯,K)是树Th的叶子结点的编号构成的油井簇,树Th的根结点为(h,sgh),sgh即为簇SSk的总存油量;选择满足sgh≤qm(m=1,2,⋯,M)的单车载重上限最小的车型车辆,完成簇SSk的集油任务。

3.2 基于油井之间路径长度、油井存油量及集油时间窗的加权距离

综合考量路径距离、集油时间窗和存油量等集油相关因素,将油井i与油井j之间的路径距离、油井j的集油时间窗ETj,LTj和油井j存油量gj的加权和作为聚类算法中从油井i到油井j的距离度量。

定义1 油井i到油井j的距离为

dfij=αdij+βgj+γ(LTj-ETj)×ETj,i,j=0,1,⋯,N-1,

其中,α、β、γ为组合系数,满足0≤α,β,γ≤1,α+β+γ=1。

3.3 初始簇中心选择

对油井集的初始簇划分SS={SS1,SS2,⋯,SSK}的每个簇SSkk=1,2,⋯,K,选择簇中与车场距离最小的油井作为簇的初始中心。

SCPk=j|df0j≤df0i 同时 j∈SSk且 i∈SSk是簇SSk中与车场距离最小的油井子集,任取cpk∈SCPk作为簇SSk的初始中心。

3.4 带约束k-means聚类算法设计

带约束k-means算法求解模型(3)主要包括“约束满足优先的油井分配”、“概率性分散的簇中心更新”和“簇内路径优化”三个步骤,三步骤循环迭代直至满足结束条件。

3.4.1 约束优先的油井分配

针对油井集的簇划分SS={SS1,SS2,⋯,SSK},依次将油井i(i=1,2,⋯,N-1)分两步分配到簇:

1)约束优先的候选簇筛选

分配油井i时,前面i-1口油井的分配已完成,簇SSk的当前存油量为sgkk=1,2,⋯,K。

油井i的候选簇必须满足簇存油量与集油车辆的最大载重相容的约束条件,因此,油井i的候选簇集合CS={SSk|sgk+gi≤qM,k=1,2,⋯,K}。

2)距离优先的簇分配

对于候选簇中的每个簇SSk∈CS,定义油井i与簇SSk的距离如下。

定义2 油井i与簇SSk的距离为

sfik=min {dij|j∈SSk}。

根据定义2,构造候选簇CS关于油井i的子集CSi={SSj|sfij≤sfil ;∀SSl∈CS};将油井i分配到候选簇子集CSi的任一簇SSr=SSr∪{i},同时更新簇SSr存油量sgr=sgr+gi,直到所有油井都分配到K个簇为止。

3.4.2 概率性分散的簇中心更新

1)从油井集SS中随机选择一口油井作为第一个簇的聚类中心,记为cc1。

2)设已选定了油井集SS的前h个簇中心CCh={cc1,cc2,⋯,cch}。

3)对油井集SS中每个油井i∉CCh,计算油井i到每个已选簇中心的距离并取最小值,记为distih=min {dij|j∈CCh}。

4)对油井集SS中所有油井i∉CCh,计算distih的平均值adh=∑i∉CChdistih。

5)选择下一个簇中心cch+1时,选中油井集SS中油井i的概率为

pih+1=(distih)2×adh,     i∉CCh,  0,                             i∈CCh。

按照油井i的概率pih+1,选择下一个聚类中心cch+1∈SS-CCh;距离已选定簇中心越远的油井被选中的概率越大,保证聚类簇中心的分散性。

6)重复步骤3)~5),直到K个簇中心都选定为止。

3.4.3 基于贪心策略的簇内路径优化

应用贪心法对集油车辆在簇SSk内的行驶路径进行优化,即求“车场→簇SSk内集油路径→集油点→车场”的最短路径,使簇SSk的集油费用最小。

1)SUk表示已集油油井,初始状态SUk=∅,SSk=nsk。

2)车辆从车场出发,首先选择SSk中与车场距离最小的油井k1集油,油井k1满足d0k1≤d0j(j∈SSk);同时,SSk=SSk-{k1},SUk=SUk∪{k1}。

3)设SSk中已有i口油井完成集油,然后选择SSk中未集油且与油井ki距离最小的油井ki+1集油,油井ki+1满足dkiki+1≤dkij(j∈SSk and j∉SUk);同时,SSk=SSk-{ki+1},SUk=SUk∪{ki+1}。

4)重复步骤3),直到SSk=∅为止。

5)车辆集油路径:车场→k1→k2→⋯→knsk→集油点→车场。

3.4.4 带约束k-means聚类算法迭代过程与收敛判断

输入:精度ε,最大迭代次数num。

输出:集油车辆调度方案,车辆集油的行驶路径,总费用。

1)应用贪心法将待集油油井集SS初始划分为K个子簇。

2)在每个子簇中,选择与车场距离最小油井作为簇的初始质心,得到初始质心集CCK⊆SS。

3)设迭代次数nc=1。

4)依据约束优先的油井分配策略,将油井集SS重新划分为K个子簇。

5)采用分散优先策略,按概率重新选择簇中心。

6)应用贪心法优化簇内车辆集油的路径。

7)计算簇内集油费用。

8)计算本次车辆调度及路径优化的集油总费用Znc。

9)若Znc-Znc-1<ε,转11)。

10)nc=nc+1,如果nc<num,转4),继续迭代;否则转11)。

11)算法结束。

4 结果与分析

某采油厂地处黄土高原山区,有3个采油队,每个采油队有1个车场、1个原油中转联合站。分属3个采油队的12 000多口油井分散在沟谷山梁间,因此,主要采用车辆运输方式集油。

4.1 数据集

数据集来自3个采油厂共12 000多口油井某个月平均每天的集油数据,集油数据集的描述如表2所示。

4.2 聚类结果评价指标

采用分簇准确率(AC)δAC、簇精度(PR)δPR召回率(RE)δRE三种评价指标,评估集油井聚类结果的有效性,三种评价指标分别定义如下:

δAC=∑i=1Kain
δPR=∑i=1Kai/(ai+bi)K,
δRE=∑i=1Kai/(ai+ci)K,

其中,n表示数据集对象个数,ai表示正确分到i子簇的油井数,bi表示误分到i子簇的油井数,ci表示本该分到i子簇但未分到的油井数,K是油井聚类子簇数。

4.3 聚类结果与分析

在集油数据集上运行传统的k-means算法,实验结果如表3所示。

在集油数据集上运行本文的带约束k-means结合贪心算法,实验结果如表4所示。

实验结果表明,3个大队的9个指标值中,三大队因为油井分布范围大、个别油井偏远、大部分油井产量较低,导致本文的带约束k-means对三大队油井的聚类结果不太理想,AC指标值略低于传统k-means算法,其他8个指标值均大于传统k-means算法,说明本文的带约束k-means结合贪心算法的聚类效果总体优于传统k-means算法。

4.4 实际应用结果

采油厂非集输油井多为低产、间歇出油井,以前的集油车辆调度及车辆行驶路线主要依赖历史经验人工确定,导致数据的实时性和合理性差、调度方案的效率和效益不高。在本文作者参与研发的《采油厂生产统计综合管理系统》中,将本文的研究成果应用于采油厂3个采油大队的集油生产业务,推行大调度体系,实行定人、定车、定井、定时、定量、定路线的“六定”模式,由车辆管理中心统一派单。分析汇总管理系统中近两年的油井集油数据和中转联合站收油数据,与应用前的数据进行比较,忽略油井产量波动、间歇采油实施、油井检修停产、自然灾害等因素影响,比较结果表明,采油厂日均集油井次由人工调度时的约930井次,降到了约760井次,日均集油井次下降约18.28%,集油车辆发车数从120车次/天,降到了85车次/天,下降约29.17%,显著降低车辆空驶率和燃油消耗,提高了生产效率和经济效益。

5 结论

本文以总费用最小化为目标,建立了带时间窗的多车型多费用不确定车辆数非满载集油问题的数学模型,设计了带约束k-means结合贪心策略的混合求解算法,应用于《采油厂生产统计综合管理系统》的集油生产业务中,显著提升了集油调度效率,降低了生产运营成本。

参考文献

[1]

轩苗苗. 基于改进遗传算法的冷链物流配送路径优化研究[D]. 淮南:安徽理工大学,2025.

[2]

丘凯. 深度强化学习在车辆路径问题中的应用研究[D]. 广州:广东财经大学,2025.

[3]

李二超,张智钊. 在线动态订单需求车辆路径规划[J]. 山东大学学报(工学版),2024,54(5):62-73.

[4]

刘狄. 考虑碳排放和服务水平的多中心配送路径优化研究[D]. 重庆:重庆交通大学,2025.

[5]

MOON I. K, LEE J-H, SEONG J. Vehicle routing problem with time windows considering overtime and outsourcing vehicles [J]. Expert Systems with Applications,2012,39(18):13202-13213.

[6]

CETINKAYA C, KARAOGLAN S, GOKCEN H. Two-stage vehicle routing problem with arc time windows: A mixed integer programming formulation and a heuristic approach [J]. European Journal of Operational Research, 2013,230(3):539-550.

[7]

GHANNADPOUR S F, NOORI S, TAVAKKOLI-MOGHADDAM R, et al. A multi objective dynamic vehicle routing problem with fuzzy time windows: Model, solution and application[J]. Applied Soft Computing,2014,14:504-527.

[8]

DHAHRI A, ZIDI K, GHEDIRA K. Variable neighborhood search based set covering ILP model for the vehicle routing problem with time windows [J]. Procedia Computer Science, 2014,V(29):844-854.

[9]

张冬梅,李敏,徐大川,等. k-均值问题的理论与算法综述[J]. 中国科学:数学,2020,50(9): 1387-1404.

[10]

赵雄,李琳. 基于聚类的LNS算法求解异构VRP问题[J]. 计算机技术与发展,2023,33(9):98-104.

[11]

朱珠,温召成,臧洁. 电子商务快递末端配送模式优化研究[J]. 武汉理工大学学报(交通科学与工程版),2024,46(1):139-145.

[12]

宋虹颖. 考虑多车型的成品油主动配送规划方法研究[D]. 长春:吉林大学,2025.

[13]

戴永寿,李韶光,李立刚 等. 基于改进k-means和遗传算法的油田特种车辆优化调度[J]. 计算机应用,2016,36(S1):86-89.

[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)

AI Summary AI Mindmap
PDF (658KB)

0

访问

0

被引

详细

导航
相关文章

AI思维导图

/

〈 〉