订单配送启发式算法

1、4.3.4配送订单分组合并审核问题的建模与启发式算法客户订单分组合并审核问题，主要是针对每个客户订单的订货量较小的情 况（小于车辆容量）设计的。此问题可描述如下：设有N个批发商，n个客户，客户 通过订单向源批发商订购产品，每个客户订单的订货量均小于任何一辆车的车辆 容量；源批发商每天都对第二天计划运送的订单进行合成，每辆汽车的容量是一 定的。进行客户订单合成配送需要使运距最短，并且满足运送日期和车辆容量、 运送路线、交货期及装货规则等约束条件。需说明的是，订单是由订单号、批发 商、订货量、客户名称、计划运送日期、交货期和交货组等7项数据组成。一个 订单只能有一种产品，同一客户处可以有多订单。其

2、中交货组是用于注明那些有 特殊要求、需要在同一车上运送的订单。本节构造了客户订单合成配送问题的数学模型，研究了解决该问题的两个阶 段启发式算法。下面还将给出一个用此算法求解该问题的例子。（一）客户订单合成配送问题的数学模型问题的假设及说明（1）模型中有N个批发商，以及n个客户，针对此种情况建立的；（2）每个订 单的订货量均小于车辆容量，每个订单只能订一种产品，同一客户有多订单的情 况；（3）所运送的产品只考虑质量的装车问题；（4）该系统仅采用一种运送方式 （即所用运输工具都属同种类型），且运输工具的数量无限制；（5）每个合成运送 的订单组合中所包含的订单的总批发商数（即发货批发商的数量）不多于

3、两个； 运输工具有最大最小能力限制。问题的参数n表示客户个数；N表示源批发商个数；L表示客户i的订单数，i=1，2， z； K是计划的组合数（车数）；W表示每辆车所能装载货物的质量的最大值；Wmin 是每辆车应该要求的装货质量的最小值；smax表示每条运送路线的最大交货的站 数；。呻表示每条运送路线上相邻两个交货站间最大距离；V表示车速，单位为 公里每小时；d表示从位置i到位置j的路径长度（图上直接距离）。决策变量X G 0,1，订单决策变量。i=1,2,.n； m=1,2,.L； k=1,2.KoX= 1表示组合中包含第m个客户的第i份订单；X=0则表示否。z为路径i jk选择变量，Z二1表

4、示在组合k中，车辆从位置1直接驶向位置j； Z =0则表示否。4.数学模型本模型中，目标是求最小化的运距，如式(1)所示；式(2)(4)则是表示路径条件。式(5)表示组合k中所有订单的订货量之和需满足质量约束。式(6)表示的是任一订单至多被分配在一个组合中。式(7)表示保证组合k中客户i的第m个订单的交货期。min 乙乙 乙 dij Zijkk =1 i = 1- N j = 2 NSubject to:E E Zi= 1, k = 1,2,., Kjki=1-N j=1E Z 1, i = 1 - N,., -1,0,1,. n ijkj = 1 Yik 5 max i=1wminEE Wm

5、 - X. W maxi=1 m=1Eximk k =1 1, i = 1,2,., n; m = 1,2,., Lih Ximk h . X. , i = 1,2,., n; m = ,2,., L(二)客户订单合成配送问题两阶段启发式算法算法步骤输入在计划运送日期内的所有订单；找出这些订单的全部可能的订单组合；依次判断以上每一个订单组合，是否满足质量约束；依次判断以上每一个订单组合，是否满足最大的交货站数约束；依次判断以上每一个订单组合，是否满足站间的最大距离约束；对于满足步骤(3)，(4)，(5)的组合，将组合中的每个订单组合排序;计算每个订单组合中由上步算出的排列顺序的距离；对于每个订

6、单组合来说，按照排列顺序的距离，以递增的顺序整理。然 后，依次检验是否满足装货规则及交货期，直到找出一个满足装货规则，和交货 期的顺序为止。如果某个订单组合找不到一个这样的顺序，则放弃这个组合。算法的优化步骤(1)对于各个订单的组合，按照它们的合法顺序计算质量/费用比；(2)对于有 特殊要求，需要分在一组的那些订单所在的订单组合，则按照计算出来的质量/ 费用比，以非递增的顺序列成清单，将其余没有特殊要求的订单，按质量/费用 比列在清单的下部；(3)将排在该清单最上面的订单组合，合并作为一组合成运 送。此时，可以将该订单组合从清单中移走。然后，对将该订单组合中剩下的那 些订单，重复使用步骤(2)

7、，直到所有订单都被划分完毕为止。算法举例现以6个订单的合并分组审核问题为例，使用该算法。订单数据见表4-11。表4-11配送订单数据Table 4-11 The Data on the Distribution Order订单号批发商总质量横坐标纵坐标计划运送日期请求交货日期1A79801101572009-2-82009-2-92B92104235232009-2-102009-2-133A12360-130-2202009-2-92009-2-114A8846-5202332009-2-82009-2-105B4570430-3532009-2-92009-2-116B6310-20134

8、02009-2-102009-2-12将上述订单上的数据输入计算机，调用启发式订单批次划分算法，可求得最 优配送方案为：ba562； a13； ba463。其含义是这6个订单需配装在3辆车中，每 辆车的运送路径分别为：BA562； A13； BA463。4.3.4配送订单分组合并审核问题的遗传算法（一）编码方法本算法采用顺序编码方法。具体步骤如下:将满足计划运送日期的订单读入， 对于有特殊要求的那些订单，则合成为一个订单读入。统计订单数n。用矢量 （Si，S2，.Sn）表示染色体。其中，元素Sj为1,n之间的一个互不重复的自然数， 它表示订单S的装货顺序优先级为j。这时，可以用一段顺序编码来表

9、示该问题 j的染色体。这里为7213465。其含义是：订单7的装货顺序优先级为1，而订单2的 装货顺序优先级为2。依此类推，订单5的装货顺序优先级为7。（二）可行化过程现在将染色体的编码向量映射为满足全部约束条件的可行解，这一过程称为 可行化。其实施步骤如下：令m=1,i=1,j=1,k=0;其中，k表示组合数。判断mn是否成立？若成立，则转3；否则，算法终止。判断是否满足同一订单组合中批发商数目小于等于2,若满足，则转4；否则，转9。判断是否满足一个订单组合中所包含的订单的客户数小于或等于最大交货站数约束？若满足，转5；否则，转9。判断是否满足任意两个相邻客户位置之间距小于等于交货站间的最大

10、距离约束？若满足，转7；否则，转9。判断是否满足装货规则约束？若满足，则根据装货规则加入源批发商，转7；否则，则转9。判断是否满足交货期约束？若满足，则转8；否则，转向步骤9。令m=m+1,然后转步骤2。输出Si,Sm-1，令i=m,k=k+1,转到步骤2.个体适应度评价本节中的遗传算法，采用比例选择算子来确定群体中各个个体遗传到下一代 群体中的数量。为了正确计算不同的情况下，各个个体的遗传概率，应要求所有 个体的适应度必须为正数或为零，而不能是负数。本问题是以最小化运输费用为 目标函数的，即优化目标是函数的最小值，为了满足适应度取非负的要求，将目 标函数值f(x)变换为个体的适应度F(x)。

11、其方法为：如果f(x)Cmax，则F(x)=0。式中，Cmax为预先指定的一个较大的 数。遗传操作选择。选择一般根据个体的适应值，按照一定的选择概率来进行。在这里，当前的 种群中的个体xi选择概率p(xi)可按式(8)来计算，其中f(xi)表示个体xi对应的适 应值：P (气)=f (气)/ 支。f ( x j )(8)j=1交叉。本算法选用部分匹配交叉的方法进行。部分的匹配交叉是指交换两个父代染 色体P2的对应部分顺序(随机产生两个位置，交换两个位置间的部分顺序)， 来产生两个子代染色体O1,O2，然后对新产生的染色体进行合法化处理的方法。变异。变异发生的概率很低，本算法经过比较后，选用的基

12、因变异概率p =0.001o m采用互换变异方式，艮即在变异概率范围内，将两个不同位置的基因进行位置交 换，以完成突变。算法实施步骤。在描述遗传算法实施步骤之前，先对算法涉及到的有关术语定义如下:Popsize表示种群的大小；t表示进化代数；T表示最大进化代数；P（t）表示第t 代种群。遗传算法的实施步骤如下：Stepl:初始化，输入订单数据和批发商数据后，判断每个订单的计划运送日期 是否大于等于计划日期？若是的话，则转Step2 ；否则，应该放弃该订单数据， 进行下一个订单数据的判断，一直到不再有订单数据为止。Step2:判断该订单是否有特殊要求，所以需和其他订单在一起运送？若有的话， 则将

13、需要合成为一个订单读入；否则，直接读入该订单数据，并统计订单数n。 Step3:设置进化代数t-0 ；设置最大进化代数T。随机产生一个初始 （Population），包括 Popsize 个的个体。Step4:针对当前种群进行可行化处理。Step5 :针对当前种群内每个解计算目标函数值。Step6 :针对当前种群内每个解计算适应值。Step7 :停止进化条件判断，测试算法是否应该结束。然后，判断迭代的代数t是 否为所要求的代数T，若是，则停止进化。选性能最好的染色体所对应的路径集 合作为问题的优化解输出。否则令t=t+1，转Step8。Step8:选择运算。对种群P（t）进行正比选择运算。Step9:交叉运算。对选择出的个体集合P（t）做部分映射交叉运算即PMX交叉。 Step10:变异运算。对P（t）做换位变异运算。群体？（t）经过选择、交叉、变 异运算之后得到下一代群体P（t+1），转Step4。为了测试该遗传算法在不同问题规模（包括订单数、交货组数）下的运行性 能