资源描述：
《配送路线选择与车辆调度备课讲稿.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、配送路线选择与车辆调度VRP问题的描述VRP问题一般可描述为：对一系列装货点或（和）卸货点，组织适当合理的行车路线，使车辆有序地通过它们，在满足一定的约束（如货物需求量、发送量，车辆容量、数目限制、车辆行驶里程限制等）条件下，达到一定的目标（如最短路程、最小费用、最短时间、最少车辆等）。2VRP问题的分类VRP问题又根据不同标准分为：车辆满载问题（一个用户的货运量大于一辆车的容量，完成任务需要多辆车）与非满载问题（一个用户的货运量不大于一辆车的容量，完成任务只需要一辆车）、单车场问题（一个货场或一
2、个配送中心）与多车场问题（多个货场或多个配送中心）、单车型（所有车辆容量相同）与多车型问题（车辆容量不全相同），以及优化目标的单目标与多目标问题。3二、VRP问题精确求解方法的局限性1.VRP问题求解思路VRP问题的求解方法一般相当复杂，通常的做法是应用相关技术将问题分解或者转化为一个或多个已经研究过的基本问题（如旅行商问题、指派问题、运输问题、最短路问题、最小费用流问题、中国邮递员问题等），再使用相对比较成熟的基本理论和方法进行求解。42.精确算法的局限性VRP问题的求解方法可分为两大类，即精确
3、算法和启发式算法。精确算法主要有分枝定界法、割平面法、网络流算法、动态规划方法等。精确算法随着配送系统规模的增大，其计算量呈指数递增，使得获取系统最优解越来越困难。因此，精确算法在实际应用中受到很大的局限。5三、节约法原理为了克服精确优化方法的不足，人们提出了许多能获得“满意”解的启发式算法。启发式算法是一种基于直观或经验构造的算法，它运用一些经验法则，并通过模仿人的跟踪校正过程来求得系统的满意解。启发式算法中最具有代表性的是由Clarke和Wright提出的节约法（SavingMethod）。6
4、节约法的基本原理：789第二节单中心配送路线选择与车辆调度10如果将配送中心也作为一个用户点，货车从配送中心出发，对所有用户巡回送货后回到配送中心，这样就把单车非满载车辆的配送路线安排问题转化为个点的旅行商问题（TravelingSalesmanProblem，简记TSP）。它的解是：从配送中心出发，对所有用户巡回一次回到配送中心的距离最短的路线。1112131415161718192021二、多车非满载配送路线安排与车辆调度222324此模型用精确算法求解更加困难，下面仍用节约法求解此类问题的满
5、意解。求解的过程与例6-1基本相同，只是在方案改进的过程中，寻找具有最大节约量的用户i、j时，增加了考虑车辆载重量和可调度车辆数的约束，而且，车辆调度时优先使用载重量大的车辆。25例：由配送中心B0向12个用户Bj(j=1,2,…12)送货，各点之间的运输里程和各用户的需求量见表6-1。表6-2为可供调度的车辆数目及其载重量。表6-1各点之间里程表（单位：公里）表6-2可供调度的汽车26解：由表6-1中的数据，按节约量公式（6.5）计算每两用户之间的节约量Si,j列于表6-3，称节约量表。表6-3
6、节约量表（单位：公里）如:S1,2＝d0,1+d0,2－d1,2＝9＋14－5＝18S2,4＝d0,2+d0,4－d2,4＝14＋23－17＝2027设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,有以下等式成立：j=1,…,
7、n（6.7）28迭代求解：第一步，求初始解每用户各派一台车单独送货，得初始方案如表6—4。表中B0列中的数字为ti,j的取值。此方案的总行程为728公里。按表6—4的初始方案，所用汽车台数如表6—5所列。29表6-4初始方案表6—5初始方案所用汽车台数30第二步，按下述条件在初始方案表中寻找具有最大节约量的用户i、j（1）t0,i、t0,j＞0i≠j；（2）Bi、Bj尚未连接在一条巡回路线中；（3）考虑车辆台数和载重量的约束。如果最大节约量有两个或两个以上相同时，可随机取一个。按此条件，在初始方案
8、表6—4中寻到具有最大节约量的一对用户为：i=11,j=12，其节约量为92公里。将11和12两用户连接到一个运输回路中，并在对应的格中记上t11,12的值，用“1）”表示。31第三步，按ti,j的定义和公式6—7修正ti,j的值。B11与B12连接，即令t11,12=1，由公式（6.7）得：t0,11=1t0,12=1其他不变。32第四步，按以下原则修正bi、bj（1）t0,i或t0,j等于0时，令bi或bj等于0；（2）t0,i或t0,j等于1时，令bi或bj等于所在巡回路线中
