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

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）。比较初始可行解和最优解的费用，最优解比可行解并 …… 此处隐藏：3134字，全部文档内容请下载后查看。喜欢就下载吧 ……