配送路线选择与车辆调度.ppt

第二节单中心配送路线选择与车辆调度*如果将配送中心也作为一个用户点，货车从配送中心出发，对所有用户巡回送货后回到配送中心，这样就把单车非满载车辆的配送路线安排问题转化为个点的旅行商问题（TravelingSalesmanProblem，简记TSP）。它的解是：从配送中心出发，对所有用户巡回一次回到配送中心的距离最短的路线。*******二、多车非满载配送路线安排与车辆调度**此模型用精确算法求解更加困难，下面仍用节约法求解此类问题的满意解。求解的过程与例6-1基本相同，只是在方案改进的过程中，寻找具有最大节约量的用户i、j时，增加了考虑车辆载重量和可调度车辆数的约束，而且，车辆调度时优先使用载重量大的车辆。例：由配送中心B0向12个用户Bj(j=1,2,…12)送货，各点之间的运输里程和各用户的需求量见表6-1。表6-2为可供调度的车辆数目及其载重量。表6-1各点之间里程表（单位：公里）表6-2可供调度的汽车表6-3节约量表（单位：公里）*解：由表6-1中的数据，按节约量公式（6.5）计算每两用户之间的节约量Si,j列于表6-3，称节约量表。如:S1,2＝d0,1+d0,2－d1,2＝9＋14－5＝18S2,4＝d0,2+d0,4－d2,4＝14＋23－17＝20设ti,j(i=0,1,…,12;j=1,2,…,12；i≠j)表示i、j两点是否连接在一起的决策变量，并对其取值作如下定义：ti,j=1表示i、j用户连接，即在同一巡回路线中；ti,j=0表示i、j用户不连接，即不在同一巡回路线中；t0,j=2表示j用户只与配送中心B。连接，由一台车单独送货。根据以上定义，对任一用户j,有以下等式成立： 1j=1,…,n（6.7）2第一步，求初始解迭代求解：*每用户各派一台车单独送货，得初始方案如表6—4。表中B0列中的数字为ti,j的取值。此方案的总行程为728公里。按表6—4的初始方案，所用汽车台数如表6—5所列。表6-4初始方案表6—5初始方案所用汽车台数*第二步，按下述条件在初始方案表中寻找具有最大节约量的用户i、j（1）t0,i、t0,j＞0 i≠j；（2）Bi、Bj尚未连接在一条巡回路线中；（3）考虑车辆台数和载重量的约束。如果最大节约量有两个或两个以上相同时，可随机取一个。按此条件，在初始方案表6—4中寻到具有最大节约量的一对用户为：i=11,j=12，其节约量为92公里。将11和12两用户连接到一个运输回路中，并在对应的格中记上t11,12的值，用“1）”表示。第三步，按ti,j的定义和公式6—7修正ti,j的值。B11与B12连接，即令t11,12=1，由公式（6.7）得：t0,11=1t0,12=1其他不变。第四步，按以下原则修正bi、bj*t0,i或t0,j等于0时，令bi或bj等于0；t0,i或t0,j等于1时，令bi或bj等于所在巡回路线中所有用户需求量之和，以此代替原bi或bj,因此b11=b12=1.1+1.7=2.8（吨）得改进方案（表6-6、表6-7）。改进后的方案比原方案少一台发送车，总发送距离减少92公里。表6-6第一次迭代方案表6-7该方案所用汽车台数*重复第二步，按下述条件在第一次迭代方案表6－6中寻找具有最大节约量的用户i、j（1）t0i、t0j＞0 i≠j；（2）Bi、Bj尚未连接在一条巡回路线上；（3）考虑车辆台数和载重量的约束。如果最大节约量有两个或两个以上相同时，可随机取一个。按此条件，在表6—6中寻得具有最大节约量的用户有两对，分别为：i=10,j=11和i=10,j=12，其节约量均为84公里，任取一对i=10,j=11，将其连接到一个回路中。重复第三步，按ti,j的定义和公式（6.7）修正ti,j的值。B10与B11连接，则t10,11=1，由公式（6.7）得：t0,11=0t0,10=1其他不变。重复第四步，按以下原则修正bi、bj*t0,i或t0,j等于0时，令bi或bj等于0；t0,i或t0,j等于1时，令bi或bj等于所在巡回路线中所有用户需求量之和，以此代替原bi或bj,因此b10=b12=2.8＋1.6=4.4（吨）b11=0得第二次迭代方案（表6-8、表6-9）。第二次迭代方案比第一次迭代方案又少一台配送车，