物流配送中心配载车辆调度问题研究

物流配送中心配载车辆调度问题研究

ComputerEngineeringandApplications计算机工程与应用

2010，46（36）237

物流配送中心配载车辆调度问题研究

谢天保，雷西玲，席文玲

XIETian-bao，LEIXi-ling，XIWen-ling

西安理工大学，西安710048

Xi’anUniversityofTechnology，Xi’an710048，China

XIETian-bao，LEIXi-ling，http://www.77cn.com.cnputerEngineeringandApplications，2010，46（36）：237-240.

Abstract：Theobjectiveoflogisticsstowageschedulingistodispatchvehicleresourcesaccordingtothespecifictaskinor-dertoreducethecost.Analyzingtheconstraintsoftransportvehiclesandspecifictask-related，themathematicalmodelofthevehicleschedulingprobleminlogisticscenterisbroughtup.Focusonthe“division”algorithmwhichisbasedontheorderofthetask-timewindow，aswellasthefeasiblesolutionintheimplementationofcross-geneticoptimizationalgorithmbasedontheprobabilityoftimewindowsrestrictionconflict.Theexperimentalresultsshowthatundermulti-taskandmulti-con-straintconditionsthisalgorithmcanbeusedquicklytostrikeanoptimalsolutionoflogisticsstowagescheduling.Keywords：cargoloading；vehiclescheduling；geneticalgorithm摘

要：物流配载车辆调度目标就是针对特定任务调配车辆资源以降低成本费用。分析了车辆和特定运输任务的相关约束条

件，提出了物流中心配载车辆调度问题数学模型。重点研究了基于任务时间窗逻辑顺序约束求取可行解的“分组”算法、以及基于时间窗约束冲突概率对可行解基因实施交叉的优化算法。实验结果表明在多任务、多约束条件下采用该算法可快速求取物流配载调度问题的最优解。

关键词：货物配载；车辆调度；遗传算法DOI：10.3778/j.issn.1002-8331.2010.36.066

文章编号：1002-8331（2010）36-0237-04

文献标识码：Ａ

中图分类号：TP391

1引言

物流配送是现代流通业的一种经营方式。物流是指物品

lem）和车辆调度问题VSP（VehicleSchedulingProblem），被认为是一个NP-hard问题[2]，只有当其规模较小时，才能求其精确解。对于求解该问题，多数文献采用的是启发式算法[3-4]，如模拟退火[5]、变邻域搜索法[6]、蚁群算法[7]等。根据配载车辆调度问题的特点，从实用角度出发，提出带时间窗口的配载车辆调度模型，并就模型的优化算法进行研究，以提高运输资源使用效率，降低物流活动成本。

物流配送中心通常会向一些站点配送货物，每个站点对货物量有一定的需求，这些货物往往具有小批量、多品种的特点，这就需要对运输车辆进行配载，配载后的车辆按照一定的运输路线把货物送到各顾客处，完成任务后返回物流中心（如图1所示），如何确定满足用户需求的费用最小的车辆行驶路线，即物流中心配载车辆调度。

从供应地向接收地实体流动的过程。在物的流动过程中，根据实际需要，包括备货、储存、分拣、配货及配送、信息处理等基本功能活动。配送指在经济合理区域范围内里，物流中心根据客户要求，对物品进行拣选、加工、包装、分割、组配（配载）等，并按时送达指定地点。配送运输属于物流活动中的末端运输，具有短距离、小规模、多客户及频度高的特点，一般使用汽车做运输工具。如何对车辆进行配载、规划最佳路线一直是物流领域研究的热点课题。

2物流配送中心配载车辆调度模型

物流配送车辆优化调度问题最早由DnaZtig和Ramser于

1959年首次提出。一般定义为：对一系列装货点和卸货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最

[1]短、费用最少、时间尽量少、使用车辆尽量少等）。物流配载

物流中心

调度包括了运输路线安排问题VRP（VehicleRoutingProb-基金项目：陕西省教育厅专项基金项目（No.8JK016）。

作者简介：谢天保，博士，副教授，研究方向：人工智能、智能电子商务及其在网络化制造中的应用。收稿日期：2009-05-25

修回日期：2009-08-31

图1物流配送路径图

物流配送中心配载车辆调度问题研究

2382010，46（36）ComputerEngineeringandApplications计算机工程与应用

设物流中心（编号为0）向N个站点送货，第i个站点的货运量为g(i)，允许车辆进入站点的最早时间为St(i)，最迟时间为Et(i)，卸货消耗时间为T(i)，各站点及物流中心的距离为D(ij)，

可用运输车辆Sk辆，第k辆车的最大运载能力为gmax(k)，平均车速v(k)，调用车辆固定费用pf(k)，车辆行驶1

公里产生的单位运输费用pc(k)，与车辆自身性能及最大载重量相关。xijk=1表示第k辆车从第i站点到第j站点(i¹j)，否则为0。yik=1表示第i个站点的货物由第k辆运载，否则为0。总费用为调用车辆固定费用与车辆运输费用之和，车辆调度的目标就是总费用最低。

对于拥有Sk辆汽车，向N个站点配送物资的物流中心，其车辆调度模型为：

min(åSk

pfSkN

k(g)´f(xijk)+k=1å

åxijk´D(ij)´pc(k))（1）

k=1ij=0

其中：只要任一xijk=1，表示第k辆车被调用，那么f(xijk)=1，否则为0。

s.t.

åN

g(i)´yik=12...Sk（2）i=1

k£gmax(k)åSk

yik=1

i=12...N

（3）k=1åNxN

ijk=åyk=12...Sk

（4）ij=0

i=1

ikSt(i)£Et(i)i=12...N

（5）

假设车辆k进入第i站点的时刻为Tki，下一个站点为i+1，那么有下列约束条件：

St(i+1)£Tki+T(i)+

D(ii+1)

£Et(i+1)

（6）

3基于遗传算法的配载车辆调度算法

遗传算法是一种“生成+检测”的迭代搜索算法，它以种群

中的所有个体为操作对象，每个个体对应问题的一个解，通过对个体交叉、变异操作更新换代以获取最优解。其主要操作步骤为：初始染色体设置、选择、交叉、变异及染色体进化等。

3.1初始染色体设置

初始染色体是问题的可行解，对于多站点、多时间窗约束

的配载车辆调度问题，直接求取可行解是比较困难的，本文提出基于约束时间窗逻辑顺序的分组求解法。按照各站点允许车辆进站最迟时间Et(i)的先后顺序对站点排序。排在最前列的1号站点列为第一组，假设车辆进入1号站点的时间为St（1），针对每辆运输车k考察1、2号站点同组是否冲突（依据公式7）判定），把不发生冲突的车号记入该组的可用车辆表，如果所有车辆都不能满足约束条件，把两个站点分为1和2两组，以此类推对后续站点进行分组，对于存在某站点i可同时分入多组的状况，继续第i+1站点分组，如果分组成功继续后续站点分组，否则考虑包含有i站点的集合，去掉i站点后尝试对i+1站点分组，如果对i+1站点分组依然失败，增加新组，把i+1站点分入新组。所有站点分组完成后，每组对应一条子路径，为每条路径分配车辆（详见3.3节步骤3路径车辆分派），便可得到可行解。具体分组算法步骤描述如下：

假设：si代表组，sj代表组内站点，（fsi，sj）为si组第sj个站点的编号，同组内的站点同路径，Fn为组数，fn（si）为si组已有的站点数，可用车辆列表fklist（si，k）表示第si组可用的第k辆

编号，fk

（si）代表si组可用的车辆数，Tempj为将要分配的站点编号：

步骤1计算各组货物总重量Tempg（si）及可用车辆完成组内运输任务的时间TempST（si，k），以第一组计算过程为例说明，总重量Tempg（si）即为组内各站点货物量之和（略去计算过程）。

si=1；sj=1Tempi=f（si，sj）

‘取si组第一站点编号

TempST=st（Tempi，1）+T（Tempi）‘第一站出站时间

kk=1

Dowhilekk£fk（si）‘对每辆车进行判定tempST（1，kk）=TempSTDowhilesj<fn（si）

sj=sj+1；Tempii=f（si，sj）；Tempk=fklist（si，kk）‘Tempk为车辆编号TempST（si，kk）=TempST+D（Tempi，Tempii）/v（Tempk）+

T（Tempii）

‘计算车辆出站时间Tempi=TempiiLoopkk=kk+1loop

步骤2判定站点Tempj分入各组是否冲突，以第一组判定过程为例说明。

si=1；kk=1

Tempg（si）=Tempg（si）+g（Tempj）Dowhilek≦fk（si）Tempk=fklist（si，kk）

‘Tempk为车辆编号

TempST（si，kk）=TempST（si，kk）+D（fn（1），Tempj）/v（Tempk）

‘计算车辆Tempk进站时间

判定车辆进站时间、载重是否可以满足约束条件IfTempST³ST（Tempj）andTempST£ET（Tempj）andTempg（si）g£gmax（Tempk）（7）

Success（Tempk）=1‘fklist（si，k）为可用车辆

Else

Success（Tempk）=0‘fklist（si，k）为不可用车辆

kk=kk+1loop

如果存在任一Success（Tempk）为1，说明采用编号为fklist（si，kk）的车辆运输，Tempj站点分组成功，可用车辆列表fklist（si，k）更新，去除所有不可用车辆，继续后续站点分组；如所有的Success（Tempk）均为0，Tempj站点分组不成功，转步骤3。

步骤3考察Tempj前一个站点Tempj－1的分组现状，假如存在Sn个组包含Tempj－1站点，如果Sn=1，转步骤4；否则随机选取其中的Sn－1组，从其站点列表中去掉Tempj－1，返回步骤2重新对Tempj分组，如果依然不成功，转步骤4。

步骤4增加新组，Tempj列为新组成员。

对各组（路径）实施车辆分派（详见3.4节步骤4）便可得到一组可行解，实际工作中当约束条件特别苛刻时（如只存在一组可行解），上述分组算法求取的“可行解”未必可行，但只需对“可行解”编码生成初始染色体，通过单亲遗传算法获取多组后代染色体，经过迭代进化，最终仍能获取可行解。采用自然数编码方式，对上述分组结果做如下处理完成初始染色体设置，例如以上分组结果为：135，84，267，初始染色体：

1

3

5

8

4

2

6

7

其中0表示物流中心，01350表示某车辆中心出发，经过

（

物流配送中心配载车辆调度问题研究

谢天保，雷西玲，席文玲：物流配送中心配载车辆调度问题研究

1、3、5站点卸货后返回中心，另一辆车同样从中心出发，经过8、4站点卸货后返回中心，依次类同。

2010，46（36）239

解”，

否则为“不可行解”，丢弃；通过计算各可行解的满意度对其进行评价，为下一次交叉处理筛选优良种群。下面叙述染色体可行性检测算法步骤：

假设Fn为染色体中的子路径个数，R代表子路径，Rji代表子路径Rj的第i站点编号，所有可用车辆中最大载重量为gmax。

步骤1载重约束检测。分别计算染色体中各子路径上所有站点货物需求量的总和sg（R）如果存在任一sg（R）j，j>gmax，3.2染色体基因交叉

自然编码的交叉主要有部分匹配交叉、顺序交叉、基于位

置的交叉以及循环交叉等。由于染色体包含了车场，两车场之间为一组，每组表示一个车辆安排路线，为了进一步优化车辆配载，这里引入“虚拟站点”概念。

定义1虚拟站点：从概念上讲虚拟站点如同其他实物站点，同样具有货物运输需求，时间窗约束限制，如果本次优化的实际站点数为N，虚拟站点编号为N+1，需求货物量g（N+1）为0，最早进入站点时间ST（N+1）=0，最迟进入站点时间ET（N+1）=M，M为一常数，其值大于max（ET（i））即可，货物卸载消耗时间T（N+1）为0。

对于N各站点、分组数为Fn的染色体，各子路径加入一个“虚拟站点”后，染色体总长度SL=N+2Fn+1，例如上例初始染色体各子路径随机加入一个虚拟站点，染色体变为：

1

3

9

5

8

4

9

2

6

9

7

为了防止一般的交叉将组混乱而产生大量不可行的解，采用单亲基因交叉概率，依据各基因（站点）的交叉概率控制基因交叉频度，可使交叉后的染色体成为可行解的可能性增大。

定义2“强”冲突：假设有i、j两个站点（ET（i）<ET（j）），运输车辆进入站点i的时间恰好为站点允许的最早时间，如果存在ST（i）+T（i）+D（i，j）/max（v（k））>ET（j），那么i、j两站点时间窗约束存在冲突，这种冲突称之“强”冲突。

定义3基因交叉概率：对于N个站点，统计计算每个站点与其他站点存在“强”冲突的频度di，p（i）=1－di（/c+max（d）i），c取1到3之间的整数，p（i）称之为第i个基因的交叉概率。显然对于某站点“强”冲突频度越高，基因交叉概率越低。

采用两种方式实现单亲基因交叉：单点交叉和块交叉。单点交叉：随机产生（1，SL）区间的两个正整数n1和n2，要求n1和n2位置上的基因（站点）不能同时为“虚拟站点”或“物流中心”，对于同一分组（路径），直接交换n1和n2所对应位置的基因；对于不同分组n1和n2，产生（0，1）之间的随机数p，如果p（n1）和p（n2）大于p，交换n1和n2位置的基因，否则不交换，如图2所示。

n1

n2n1n20

1

3

9

5

8

4

9

2

6

9

7

图2染色体基因基因交叉

块交叉：类似于点交叉，产生随机数，确定同一（或不同路径）的两个区间，同一路径内区间块直接交叉；不同路径内的区间块，产生（0，1）之间的随机数p，如果两个区间块内各基因交叉概率均大于p，两个区间块实施交叉。

3.3染色体的检测与评价

初始染色体在经过基因交叉处理后，得到若干组染色体，

染色体中的“0”代表物流中心，连续两个“0”之间的基因排列代表一子路径，即某车辆行程安排，检测是指考虑车辆的速度和载重是否满足行程安排的时间窗和车辆配载约束，如果某染色体所有子路径均满足约束条件，那么该染色体为“可行

那么该染色体为不可行解，丢弃。

步骤2时间窗约束检测。针对每个子路径Rj，考虑所有载重大于sg（R）j的车辆k，以路径中排列第一站点允许进站的最早时间St（Rj1）开始计时卸货，然后开往下一站点Rji+1，计算车辆进入站点的时间TempST，依据公式（7）判定，该车辆是否满足该站点的时间窗约束条件，如果满足考虑下一个站点是否满足，当所有站点都满足约束条件时，该车辆编号k记入可用车辆列表fklist（Rj，k）；如果存在任一站点约束条件不能满足，考虑下一个车辆，按照上述检测过程再次从子路径的第一站点开始检测，重复上述过程。所有车辆检测后，如果任一子路径的可用车辆列表fklist（Rj，k）为空，即没有车辆能满足Rj子路径约束条件，那么该染色体为不可行解，丢弃。

步骤3路径车辆分派。计算各子路径行驶路程LRj

，按照

LRj

的大小对子路径Rj进行从大到小排序。针对各子路径Rj

选取可用车辆列表fklist（Rj，k）中PCk最小的车辆完成任务，其他路径可用车辆表fklist（Rj，k）更新，去掉该车辆编号，依次类推。如果存在任一子路径未分派到运输车辆，该染色体丢弃。

每条子路径车辆确定后，就可以计算各子路径的费用，进而计算各染色体的适应度。

步骤4计算染色体的适应度。路径的费用总和=固定费用+运输费用

åFnPCFn

j+=1

åLj=1

Rj

´PCjj

利用某一较大的常数减去路径费用即就是染色体的适应度。

计算各染色体的适应度，选取适应度高的染色体作为新种群，反复进行交叉、检测与评价迭代运算，最终获取最优解。

4实验分析

假设某一物流中心现有8个站点需要运输货物（虚拟站

点编号9），各站点对货物的需求量及车辆进站要求的时间窗信息如表1（站点编号以按最迟进站时间排序）：

表1

站点对货物需求量及进站时间窗约束

站点编号

货物量/t

最早进站时间

最迟进站时间

货物卸载时间

12.02.03.00.524.02.04.03.033.02.04.00.844.52.54.51.053.53.05.01.061.53.05.52.073.05.07.02.582.56.08.03.09

20.0

物流中心及各站点之间的距离信息如表2所示（物流中心编号0，距离单位公里）。物流中心现有5辆可派遣的运货客车，各运输车辆相关信息如表3所示。

物流配送中心配载车辆调度问题研究

2402010，46（36）

表2

站点编号

0123456789

0040100807560100901250

ComputerEngineeringandApplications计算机工程与应用

km

8125110701009075907500

90000000000

1

2路径1

7

4

6路径2

8

3

5路径3

物流中心及各站点之间的距离信息

1400701004065701001100

210070010090757075700

380100100012075751001000

475409012007550100900

560657575750100100750

6100707075501000100900

790100751001001001000750

图4最优解路径划分

路径1、2、3中的行程分别为275、340和215，货物量分别

为9吨、8.5吨和6.5吨，运输任务分别由3、4、5号车完成，最优解的总费用为：1710元，其中固定费用不变，运输费用（275×1.8+340×1.6+215×1.4）。比较初始可行解和最优解的费用，最优解比可行解并没有降低多少费用，这是因为受车辆资源和任务时间窗约束，采用分组法求出的初始可行解已经接近最优（特别是车辆配载和时间窗约束条件比较苛刻），因此只需较少次数的迭代进化运算，便可获取最优解。

表3

车辆编号12345

车辆最大载量/t12111098

各运输车辆相关信息

车辆行驶平均速度（/km·h）

120120110100100

-1

车辆固定费用/元200150130120120

车辆每公里运输费用/元

2.52.01.81.61.4

5结论

物流中心车辆配载调度一直是物流领域研究的热点课题。首先分析了多车辆、多任务约束的车辆配载调度模型，然后依据站点任务时间窗约束、车辆载重约束条件采用“分组”算法求取可行解，在此基础上通过对可行解实施单亲遗传算法最后获取最优解。实验结果表明采用该模型算法可快速求取车辆调度问题的最优解。

根据以上站点货物需求、时间约束及可用车辆信息，采用3.1节提出的分组算法，前7个站点分组结果为{1，2，7}，{3，4，6}和{5，6}，6号站点可同时分入两组，继续第8号站点分组，8号站点只能分入{5，6，8}，从{3，4，6}组去掉6号站点，得到可行解如图3所示。

1

2路径1

7

5

6路径2

8

3

4路径3

参考文献：

[1]冯辉宗.制造系统敏捷供应链的物流配送优化调度技术研究[D].

重庆：重庆大学，2004.

[2]张潜，高立群.物流配送路径多目标优化的聚类—改进遗传算法[J].

控制与决策，2003，18（4）：418-422.

[3]BentR，VanHentenryckP.Atwo-stagehybridalgorithmforpick-upanddeliveryvehicleroutingproblemswithtimewindows[J].ComputersandOperationsResearch，2006，33（4）：875-893.[4]DondoR，CarlosA.Optimalmanagementoflogisticactivities

inmulti-siteenvironments[J].ComputersandChemicalEngineer-ing，2008，32：2547-2569.

[5]BellJE，McMullenPR.Antcolonyoptimizationtechniquesfor

thevehicleroutingproblem[J].AdvancedEngineeringInfomat-ics，2004，18：41-48.

[6]RopkeS，PisingerD.Anadaptivelargeneighhourhoodseachheu-risticforthepickupanddeliveryproblemwithtimewindows[J].TransportationScience，2006，40：455-472.

[7]李梅娟，陈雪波，张梅凤.基于群集智能算法的路径规划问题[J].清

华大学学报，2007，47（S2）：1770-1773.（

5）：1337-1348.

[3]史佩昌，王怀民，蒋杰，等.面向云计算的网络化平台研究与实现[J].

计算机工程与科学，2009，31（A1）：249-252.

[4]BuyyaR，YeoCS，VenugopalS.Market-orientedcloudcomput-ing：Vision，hype，andrealityfordeliveringITservicesascom-putingutilities[C]//Procofthe9thIEEE/ACMIntlSymposiumonClusterComputingandtheGrid，Shanghai，China，2008.[5]BuyyaR，PandeyS，VecchiolaC.Cloudbustoolkitformarket-orientedcloudcomputing[C]//Procofthe1stIntlConfonCloudComputing，Beijing，China，2009.

[6]BenioffM，AdlerC.Behindthecloud[M].SanFrancisco：Jossey-Bass，2009.

[7]ArrowKJ，LindRC.Uncertaintyandtheevaluationofpublic

investmentdecisions[J].AmericanEconomicReview，1970，60（3）：364-368.

[8]SchmidtKD.Lecturesonrisktheory[M].Stuttgart：Teubner，1996.[9]程士宏.测度论与概率论基础[M].北京：北京大学出版社，2004.

图3初始可行解路径划分

路径1、2、3的行程分别为275、375和275，货物量分别为9吨、7.5吨和7.5吨，可用车辆列表分别为{1，2，3，4}、{1，2，3，4，5}和{1，2，3，4，5}，采用3.4节中步骤4路径车辆分配法可知，路径1、2、3运输任务分别由3、5、4号车完成，可行解的总费用为：1830元，其中固定费用（130+120+120），运输费用（275×1.8+375×1.4+275×1.6），对初始染色体实施基因交叉，可获取多组可行解，检测与评价后反复迭代，随着染色体交叉、进化，种群中的染色体逐渐增多，每次迭代选取适应度最大的前20染色体实施基因交叉算法，经过10次迭代后可求取最优解如图4所示。（上接236页）

此之上，论文对担保方所面临的破产风险进行了分析，并通过实验仿真验证了引入担保为云计算平台所带来的诸多变化。仿真结果显示，引入担保后，用户的累积损失过程趋向光滑，风险承受能力显著增强，总体的协作发生率明显增加。

可以预测，随着云计算平台向市场化、社会化发展，基于担保的信用体系将大有用武之地。但是，引入担保的同时也会带来针对担保方的网络攻击行为，部分恶意用户和云服务会联合起来，通过制造虚假的索赔案例骗取赔偿金。对此，需要从用户行为分析、用户可靠度评估、云市场立法等角度展开研究，预防和惩戒骗保行为。

参考文献：

[1]BossG，MalladiP，QuanD，etal.IBMwhitepaper：Cloudcom-puting[DB/OL].（2007）.http：//http://www.77cn.com.cn.

[2]陈康，郑纬民.云计算：系统实例与研究现状[J].软件学报，2009，

20

本文来源：https://www.bwwdw.com/article/ench.html