物流工程（第三章）配车配送计划

《物流工程（第三章）配车配送计划》由会员分享，可在线阅读，更多相关《物流工程（第三章）配车配送计划（10页珍藏版）》请在金锄头文库上搜索。

1、 物流工程分析方法 第三章 配车配送计划 第三章第三章 配车配送计划配车配送计划 3.1 基本的考虑方法基本的考虑方法 城市内的集配卡车的行动，往往需要访问多个客户。例如，在商品配送基地 （deport）将商品装上卡车，随后访问多个客户，依次配送商品，而后返回同一个 配送基地。集货的情况下也是类似，从配送中心出发，依次访问客户收取货物，而 后返回统一配送基地。 上述类型的配车配送问题，是在巡回配送的情况下，分别对于不同车辆的路径 进行优化。其给定的前提条件为：客户的位置、道路网络的情况、通过路段所需时 间、交通管制信息等。在这些基本信息的基础上，加上每天的客户运送请求、时间 的要求、指定驾驶员

2、等信息，经过运算获得车辆的路线计划方案。以前，这种工作 是通过手工作业来加以完成，即使是有经验的调度人员也是需要相当的时间。现 在，通过计算机软件，在很短的时间内就可以获得总运输费用、不同车辆的累计运 行里程、累计配送时间、装载效率等数据，从而使得定量的配送计划评价得以进 行。 3.2 巡回邮递员问题巡回邮递员问题 配车配送规划（VRP: vehicle routing and scheduling problem）问题一直属于 OR （operations research）问题的研究领域。首先介绍配车配送问题的原始问题邮 递员问题。 邮递员问题的数学模型如下所述。 设有 n个城市，给定了从

3、城市 i 到城市 j 的费用 cij。某个邮递员需要从其中一个 城市出发，对每一个城市访问一次（且只访问一次），然后返回出发的城市。从可 能的路线中寻找费用最小的路线。 () )5 . 3(,1 , 0 )4 . 3(,1 )3 . 3(1 )2 . 3(1. . ) 1 . 3( 1 1 11 Njix NSSNSx Njx Nixts xcZMin ij SiSNj ij n i ij n j ij n i n j ijij = = = = = = 对于上述问题的数学表达式为如下： 1 物流工程分析方法 第三章 配车配送计划 其中，有： Z：总费用 cij：从城市 I 到城市 j 的费用。

4、 xij：当路线通过边(I,j)时为 1，否则为 0。 N：城市节点的集合=1，2，3，n S：为 N的部分集合（不是空集合，也不等于 N）。 公式（3.2）表达的从城市 I 到其它城市的路径只有 1条，而公式(3.3)表达的是 到达城市 j 的路径只有 1 条。而公式(3.4)所表达的是：路径需要通过每个城市 1 次，且指通过一次，图中不能中断。公式(3.4)中的为集合减法。公式(3.4)也可以 表达为： ()6 . 3(2 ,1nSNSSNSSx SiSj ij 在公式(3.4)或（3.6）中，禁止如图 3.1所示的局部回路出现，同时，|S|表示集合 S的元素的数量（cardinality

5、）。图 3.1中，显示了访问 4个城市的路径，在这一路 径中，有： 112 0 = = Sx x SiSj ij SiNSj ij 因此不满足公式（3.4）（3.6）。 12 34 图 3.1 部分回路（subtour）的情况 3.3 配车配送计划配车配送计划 某个运输企业具有一个配送中心，m 台卡车。从配送中心出发，采用多台卡车 给 n 个客户送货（或者从 n 个客户那里集货）。这时，每台卡车从配送中心出发， 访问多个客户之后返回配送中心。针对这种情况，试图进行如下决策：合理的决定 每台卡车的客户分组，并确定卡车的形式路径。 图 3.2.显示了配车配送问题的事例，这里 m=5，n=8。在可供

6、使用的 5台车中， 使用 2 台车辆完成 8个客户的配送任务，其行车路线如图所示。 2 物流工程分析方法 第三章 配车配送计划 卡车 2 卡车 1 中心 图 3.2.配车配送问题的事例 对于这种基本的配车配送问题，为了进一步适应实际问题，往往需要追加如下 要求： （1） 对于每个顾客存在服务时间的限定。 （2） 有多个配送中心存在。 （3） 路段所需时间将在不同时段发生变动。 考虑这样一些问题的配车配送问题将在以下加以讨论。 3.4 具有限定时间的确定型配车配送计划具有限定时间的确定型配车配送计划 3.4.1 问题的数学模型问题的数学模型 当存在各个客户接受服务的时间要求，同时配送中心、客户之

7、间的通行所需时 间为事先给定的确定数值，对于这样的问题称为具有限定时间的确定型配车配送计 划（FVRP-TW: forecasted vehicle routing and scheduling problem with time window）。在这一问题中，采用总费用作为目标函数，考虑对于这一目标函数的最 小化问题。 ()( )()()7 . 3(, 11 0, 1 0 ,0 = += m l m l lllp m l llltlllf xtCxtCxcXtCMin vvv v v 其中， () ( ) ( ) ()() () () ( )( )( ) ( ) ( )( )( )( )9

8、. 3(, 0max, 0max, )8 . 3(1, 0 0,0,0, 0 1,0, = = + += += l l N i ll a inl s inine e inll a inlindlllp N i incinlltlllt xtttctxttcxtC tinintTcxtC vvv v 上式服从如下条件： 3 物流工程分析方法 第三章 配车配送计划 ( )() ( ) ( ) ( ) )15. 3( )14. 3( )13. 3( )12. 3( )11. 3( )10. 3(2 0, 0, , 1 , 0 el ls lcll ll xin m l l l tt tt WxW x

9、WinD NN n l = = = v v v 其中， ( ) ( ) ()() () () ( ) ( ) ( ) lll l l l N i incinlll njNijdinx lx mlxXXin X mlttlt XtC tinintTtt l , 0 0,00 0 0 1.,0,0, , 1, 1, , 1 , 1 , )16. 3(1, = = = += = + v v v vv v vv v v 问顺序的数列，的配送路线的顾客和访：表示分配给卡车 中），必须被包含在（所有的 访问顺序的数列配送路线的顾客分配及：表示针对所有卡车的 ，从中心出发时间的向量：表示卡车 ：总费用 n(

10、i)：某卡车第I个访问的顾客的节点编号。 d(j)：某卡车第j个访问的配送中心的编号（这里=0）。 Nl：卡车l所访问的顾客总数。 ( )的个数。中的：数列jdxn ll v , 0 m：可能使用的卡车台数的上限。 ( ) () () ( ) ( ) ( ) ( ) ()() ( ) ( )() ( ) ( ) ( )( ) ( ) ( )( ) ( ) ( )( )( )的时刻到达节点从配送中心出发的话，于：卡车 值。的单位时间早到的惩罚：对于顾客 值。的单位时间延误的惩罚：对于顾客 的货物装卸时间。：在顾客 的平均所需时间。到顾客从顾客卡车：时刻 的出发时间。从顾客：卡车 的单位时间运行费

11、用。：卡车 的惩罚函数值：卡车 的运行费用：卡车 其它情况下 时使用卡车 的固定费用：卡车 intlxtt intc intc int ninltinintT inlt lc lxtC lxtC l x lc lll a inl ine ind inc inlinl inl lt lllp lllt ll lf 0,0, , , , , , , 0, 0, , , 11, , , 0 1 v v v v + = N：顾客的总数。 D(n(I)：顾客n(I)的需求。 4 物流工程分析方法 第三章 配车配送计划 返回配送中心的时刻。：卡车ltl 0 , ts：卡车出勤可能时间的开始时刻。 te：卡

12、车出勤可能时间的终止时刻。 ( ) 的载重量。：卡车 的装载量。：卡车 lW lxW lc ll , v 公式（3.7）说明总费用的最小化，右侧第1项是卡车的固定费用，第2项是卡 车的运行费用，第3项表示对于不满足时间窗情况下的惩罚。在卡车的运行中，具 有与运行时间无关的的固定费用，以及随运行时间变化的运行费用。 固定费用包括车辆费、税金、保险等，运行费包括油料费、修理费、轮胎费 用、人力费、道路收费等。惩罚函数在早到顾客处情况下为机会损失费用，晚到情 况下为误点损失费用。 一般情况下，可以采用如图3.3所示的惩罚函数形式。 费用 Cd,n(I) 时间 Ce,n(I) 1 1 图 3.3 惩罚

13、函数 3.4.2 问题的解法问题的解法 上述FVRP-TW为NP困难（non-deterministic polynomial hard）的组合优化问 题，难以求得严密解，因此不得不采用试探方法（heuristics）求解近似解。 试探方法多种形式，在FVRP-TW问题上经常使用的有：遗传算法（GA: genetic algorithms）、模拟退火法（SA: simulated annealing）、TS（TS: tabu search）等。 遗传算法是模拟生物进化过程的优化搜索方法，首先决定各个体（individual） 的染色体（chromosome）。而染色体则由多个遗传因子（gene

14、）所构成，染色体的 内部特征被称为遗传因子类型（genotype）。 图3.4.表示了配车配送计划中的遗传因子类型。在图中可以看到，遗传因子类 型所反映的是，从配送中心（节点0）出发，巡回顾客1-5之后返回同一个配送中 心，这样一种卡车的运行动作。 0 521340 图 3.4. 配车配送计划中遗传因子类 产生多个具有遗传因子类型的个体，实施淘汰（selection）以及增殖 （multiplication）。这时需要计算各个个体的适应度，适应度高的个体将在下一代 5 物流工程分析方法 第三章 配车配送计划 中继续生存。作为适应度可以作如下考虑：例如对于采用公式(3.7)的总费用最小化 问题，

15、可以将总费用的逆数作为适应度。仅选择适应度高的个体在下一代中生存的 话，有可能陷于局部解而无法达到真正的最优解，为此，在遗传算法中令部分遗传 因子类型进行交叉（crossover）或突然变异（mutation）。交叉的类型可以有1点交 叉、2点交叉、一样交叉、顺序交叉等。交叉或变异的比率称为交叉率或突然变异 率，需要根据不同问题加以决定。 SA是模拟固体的退火过程的算法，用于求解组合优化问题。在热力学中，在温 度t条件下相应于能量大小E的增加概率由以下公式给出。 ()17. 3(exp = kt E Ep 这里，k为波茨曼常数。将热力学中的能量置换成为组合优化问题中的目标函 数，就可以采用类似的方法求解组合优化问题。 例如在图3.5.中，设目标函数的变化量为E。考虑从当前解A向邻解B是否 进行移动时，当E0时，B位置的目标函数值小于或者等于A位置的目标函数 值，所以确定向B移动。 E D C B A 图 3.5. 模拟退火法目标函数的示例 而在确定是否从位置C向位置D移动时，由于当前位置的E0，需要根据 以下的概率值决定是否移动。 ()18. 3(exp = T E Ep 上式中T为假想温度。 也就是说，虽然D未知的目