第11章-线路规划

第十一章运输与配送的线路规划合理的运行路线和时间安排原则点点间运输——最短路径求解方法多点间运输——运输算法节约法制定车辆运行路线中国邮路法制定车辆运行路线扫描法制定车辆运行路线车辆运行时间的安排案例1伊万斯维尔地方学区为小学生提供校车服务。如图所示，现有一辆校车被分派到该地区。已知每年学生的新名册，接送学生的停车点位置在地图上标出。对各站点进行排序以确定校车每次行驶所需的时间和距离。利用你最佳的感知技巧设计满足下列条件的最短路径：经过所有停车点。孩子们可以在街道的任何一边上下车。住在临近街区的孩子可以在拐弯处上下车。不允许转U形弯。校车有足够空间，可以接送路上所有的学生。借助尺子计算校车行驶的总距离。校车路线制定练习123456789101112141315161718192021习题4答案1.将相互接近的停留点的货物装在一辆车上运送2.将集聚在一起的停留点安排同一天送货3.运行路线从离仓库最远的停留点开始。4.一辆运货车顺次途经各停留点的路线要成泪滴状。5.尽可能使用最大的车辆进行运送。6.取货、送货应该混合安排，不应该在完成全部送货任务之后再取货。7.对偏离集聚停留点路线远的单独的停留点可应用另一个送货方案。8.应当避免停留点工作时间太短的约束。一.合理的运行路线和时间安排原则1.将相互接近的停留点的货物装在一辆车上运送

仓库差的串联仓库更好的串联车辆将停留点串起来的示意图

DD仓库停留点仓库2.将集聚在一起的停留点安排同一天送货

不合理的—路线交叉划分方式较合理的—线路划分方式一周各天停留点群的划分FFFFFFFTTTTTTTD仓库FFFFFTTTFTFTTTD仓库(a)(b)停留点3.运行路线从离仓库最远的停留点开始。首先应划分出离仓库最远的停留点集聚区。选定距该核心停留点最近的一些停留点形成停留点集聚区，分派载货能力能满足该停留点集聚区需要的卡车。从还没有分派车辆的其他停留点中找出距仓库最远的站点，分派另一车辆。4.一辆运货车顺次途经各停留点的路线要成泪滴状。根据经验，当运行路线不发生交叉时，经过各停留点的次序是合理的，同时，应尽量使运行路线形成泪滴状。运输路线示意图

不好的线路规划—线路交叉

好的线路规划—线路不交叉

仓库

仓库

［例］安休瑟—布喜公司(Anheuser—BuschCompany)利用售货员通过流动卡车销售啤酒和其它饮料，卡车由当地经销人员所有。公司售货员同当地经销人员一样都是收取佣金，因而都不希望每天向各客户提供服务时花费不必要的时间，行走多余的路程。他们将图钉固定在地图上，以确定某推销员现有客户的位置。图中所举的是一个20个客户的例子，客户点的信息已经被转换到网格地图上，图中的坐标与距离相关。我们要找出的是，卡车从仓库出发，经过所有的客户点，再回到仓库，这个运行过程中距离最短的路径。建议的路径

用软件ROUTE的计算结果。整个行程的总成本为37.59距离单位。

比例尺：1＝5英里珠宝推销员问题中客户(X)和汽车旅馆(Y)的位置习题丹·帕普(DanPupp)是个珠宝推销员，他需要走访中西部的店铺。图中列出了他负责的某个销售区域。他的工作方式是在走访的前一天晚上来到这个地区，住在当地的汽车旅馆里，花两天时间走访这个地区，随后在第三天早上离开。由于是自己付费，他希望总成本能够最小。第一天要走访第1至第9位客户，第二天走访其余的客户。他有两个方案可供比较。方案1：三晚都住在汽车旅馆M2中，住宿费是每晚49.00美元。方案2：前两晚都住在汽车旅馆M1中，走访客户l至9，住宿费为每晚40.00美元。随后，搬到汽车旅馆M3住一晚，走访客户10至18，住宿费是每晚45.00美元。在走访客户l至9后，推销员回到M1，在此过夜。随后，搬到M3，过夜并于次日早晨离开。M1和M3相距36英里。不管丹在这个地区的什么地方，旅行成本都是0.30美元／英里。哪个方案对丹最好?答案方案1

路线停留点顺序距离

86412357995.4010131417181612151186.46线路总长度（英里）181.86方案1的总成本为：住宿费：49×3＝147美元旅行费用：181.86×0.30＝54.56美元总成本：201.56美元答案方案2

路线停留点顺序距离

23579864195.4018171314101115121680.30M1与M3距离36线路总长度（英里）211.70方案1的总成本为：住宿费：40+40+45＝125美元旅行费用：211.70×0.30＝63.51美元总成本：188.51美元采用第二种方案最好实例凯斯寿材公司(TheCaseCasketCompany)生产一系列殡葬产品，并向各殡仪馆送货。殡仪馆订货量常常很小，经常一次不超过一个。为服务市场，凯斯公司在全美建立了50多家配送仓库。图中列出了其中一家仓库的位置及其服务区域，同时还列出了有代表性的一周订货量和订货点的位置。仓库使用两辆特制的卡车送货，该种卡车最多可运送18副棺木，每周送货五天。要求制定出该地区的车辆路线和时刻表。

殡仪馆的位置及其一周的订货量——凯斯寿材公司密歇根中部地区首先要将该区域划分为五个每日的客户群；对每组站点的货运量进行平衡；将凯斯寿材公司密歇根中部销售区的客户按一周的五个工作日划分群组安排车辆装运，设计行车线路。凯斯寿材公司每天卡车送货的路线设计二.点点间运输——最短路径求解方法

（配送货物由一个配送中心直达某客户）最短路问题的含义最短路问题的基本原型求解最短路问题的算法1.最短路问题的含义连通图的最短路问题指求两个顶点间长度最短的路径。对最短路径问题的描述如下：

假设有一n个节点和m条弧的连通图G(Vn，Em)，并且图中的每条弧（i，j）都有一个长度cij（或者费用cij），则最短路径问题为：在连通图G中找到一条从节点1到节点n距离最短（或费用最低）的路径。用数学方法表达是：

存在连通图G(Vn，Em)，且长度矩阵C={cij│1≤i≤n，1≤j≤n│}目标函数：sabcdeft98774564565742.最短路问题的基本原型对工程实际的研究和抽象，在最短路径问题中有3种基本原型：连通图G(Vn，Em)中，从指定起始点到指定目的点之间的最短路径。连通图G(Vn，Em)中，从指定起始点到其余所有节点之间的最短路径。连通图G(Vn，Em)中，所有任意两点之间的最短路径。sabcdeft98774564565743.求解最短路问题的算法Dijkstra算法

标号设定法、标号修正法逐次逼近法Floyd算法sabcdeft9877456456574574810916sabcdeft9877456456574指起始点或目的点不唯一的运输调配问题。多点间运输中最常见的问题是产销平衡问题。

设计的总供应能力和总需求是一样，但是由不同的路径进行配送时，会导致最终的总运输成本不一样，此类问题的目标就是寻找最低的总运输成本。三.

多点间运输——运输算法有m个已知的供应点A={a1，a2，…，am}，有n个已知的需求点B={b1，b2，…，bn}，它们之间有一系列代表距离或成本的权重值cij连接起来。数学模型：条件变量：A：供应点的供应能力矩阵B：需求点的需求矩阵C：运输距离或成本矩阵决策变量：xij=从ai到bj的发送量a1a2amb1bncij供应点需求点……目标函数满足a1a2amb1bncij供应点需求点……多点间运输调配问题的求解方法单纯形法表上作业法（运输算法）运用相关软件TRANLP(LOGWARE)求法相对精确，但计算冗长，一般需借助计算机进行计算。将运输问题用表格的形式来描述，求解过程方便直观，计算量不大，可用手工直接完成，适合于简单问题的求解。［例］一制造商有三个工厂分别是1、2、3，且同时有三家供应商A、B、C。工厂1、2、3的需求量分别为600、500、300（重量单位），而A、B、C的供应量分别也有限制。A最大的供应量为400，B最大的供应量为700，C最大的供应量为500。每一供应商到每个工厂单位质量的运输成本如下图所示。工厂1需求量=600工厂

2需求量=500工厂3需求量=300供应商

A供应量

400供应商

C供应量

500供应商

B供应量

7004a76555958a供应商A到工厂

1的最佳路径的运费率，以美元/吨为单位计算.TRANLP问题的建立解决利用TRANLP（LOGWARE）软件可以解决这个问题

物流配送车辆优化调度的研究动态和水平问题的提出分类模型基本问题与基本方法算法1.问题的提出定义对一系列装货点和(或)卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量，发送量，交发货时间，车辆容量限制，行驶里程限制，时间限制等)下，达到一定的目标（如里程最短，费用最少，时间尽量少，车队规模尽量小，车辆利用率高等）。运用VRP模型车辆线路安排问题(VehicleRoutingProblem)2.VRP问题的分类按任务特征分纯装问题或纯卸问题(purepickuporpuredelivery)装卸混合问题(combinedpickupanddelivery)按任务性质分对弧服务问题（CPP）、对点服务问题(TSP)、混合服务问题(交通路线安排)

按车辆载货状况分满载问题、非满载问题接车场(或货场、配送中心等)数目分单车场问题、多车场问题按车辆对车场的所属关系分车辆开放问题、车辆封闭问题按车辆类型数目分单车型问题、多车型问题按优化目标数来分单目标问题、多目标问题3.VRP模型基本条件

现有m辆车辆停在一个共同的源点v0，给n个顾客提供货物，顾客为v1，v2，…，vn。模型目标确定所需车辆的数目N，并指派这些车辆到一个回路中，同时包括回路内的路径安排和调度，使得运输费用C最小。限制条件

N≤m

；每一个定单都要完成；每辆车完成任务后都要回到源点v0；

不能超过每辆车的容量限制；特殊问题还需考虑时窗的限制；运输规章的限制。4.基本问题与基本方法常用的基本问题有：常用的基本理论和方法有：

旅行商问题、分派问题、运输问题、背包问题、最短路问题、最小费用流问题、中国邮路问题等。分枝定界法、割平面法、线性规划法、动态规划法、匹配理论、对偶理论、组合理论、线搜索技术、列生成技术、概率分析、统计分析、最差情况分析、经验分析等。四.

节约法制定车辆运行路线旅行商问题概述TSP的启发式算法配送路线与车辆调度1.旅行商问题概述旅行商问题（TravelingSalesmanProblem，TSP）

TSP问题一般描述为：旅行商从驻地出发，经所要去的城市至少一次后返回原地，应如何安排其旅行路线，才能使总的旅行距离最少。2.TSP的启发式算法启发式算法中最具有代表性的就是由克拉克(clarke)和怀特(wright)提出的节约法(SavingMethod)（C－W算法）。节约法可以同时确定路线和经过各站点的顺序。节约法的目标是使所有车辆行驶的总里程最短，并进而为所有站点提供服务的卡车数量最少。

节约法思考的基本方法设配送中心是P0，m个用户分别是P1，P2，…，Pm

；Pi和Pj之间的最短距离是di,j

，且di,j已知(i,j=1，2，…m)。若发送车辆的吨位已知，且每辆车都可满载，则研究的目标是使所有参加发送的车辆的总发送距离在满足约束条件的基础上最小。在考虑配送计划时，首先假定在任何情况下，运输网络中的任意两点都有路径可以连通，并且都有最短路线。

节约法的思路首先假设每一个站点都有一辆虚拟的卡车提供服务，随后返回仓库,这时的路线里程是最长的。下一步，将两个站点合并到同一条行车路线上，减少一辆运输车，相应地缩短路线里程。

总结：

节约算法的基本思想是首先把各点单独与源点0相连，构成1条仅含一个点的线路。总费用为：然后计算将点i和j连接在一条线路上费用的“节约值”：s(i，j)越大，说明把i和j连接在一起时总路程减少越多。3.配送路线与车辆调度配送路线与车辆调整前提条件简单配送路线的制订理想状态下的车辆调度有装载限制的配送路线的制订(1)

配送路线与车辆调整前提条件配送路线前提假设配送的是同一种或者相类似的物资；各个用户的位置及需求量已知；从流通中心到各个用户之间的运输距离已知；流通中心有足够的资源和运力等。

车辆调整条件假设车辆调度问题一般设有一个中心，拥有容量为q的车辆若干，现在有n项运输任务(记为1，…，n，)要完成，已知任务i的货运量是gi(i=1，…，n)，且有gi<q，求满足货运需求的费用最小的车辆行驶路线。车辆调度一般要符合下列条件：满足所有需求点(用户)的需求；各种类型的车辆数目一定，能满足运输要求，完成任务；每一辆发送车辆的装载量有一定的限制，不能超载运行；对每辆发送车每天总运行时间及运行里程有预定的上限；方案能满足所有用户提出的到货时间要求。

(2)简单配送路线的制订配送问题：在一个配送中心P有一辆容量为q的货车，现在有n个用户的货运任务需要完成，已知用户i的货运量是gi

(i=1，…，n)，且有：求在满足各个用户需求的条件下，总发送距离最短的货车送货路线。思路首先，把各个点单独与配送中心相连，构建仅含一个点的初始路线，得到费用：然后，计算如果连接点i和点j到同一条线路上得到的节约值：具体步骤

:1．计算节约值s(i，j)，令集合S={s(i，j)|s(i，j)>0}；2．对集合S中的元素按从大到小的顺序排序；3．如果集合S=Φ，计算结束，否则对第一个元素s(i，j)，考查对应的(i，j)，是否满足下列条件之一：点i和点j都不在已经构成的线路上；点i和点j中一点是已构成线路的外点，另一点不在线路上；点i和点j分别是已构成的两条线路的外点，其中一个是线路的起点，另一个是线路的终点(0→j→…→0、0→…→i→0，或0→i→…→0、0→…→j→0)。转下步，否则转步骤5；4．连接点i和点j到同一条线路上；5．令S：S－s(i，j)，转步骤3。

配送中心与用户之间的距离

中心0用户19用户1用户269用户2用户310168用户3用户41318104用户4用户5148111819用户5用户61312812129用户6用户7181513171696用户7已知配送中心P（标记为中心0）和7个用户之间的距离，要求合理安排行车路线，使距离最短。

用户连接的费用节约值：

(i,j)(6,7)(5,7)(3,4)(5,6)(4,7)(1,5)(4,6)(1,7)(2,6)(3,6)(2,7)s(ij)2523191815151412111111(i,j)(3,7)(1,6)(2,4)(2,5)(2,3)(4,5)(3,5)(1,2)(1,4)(1,3)

s(ij)111099886643

0－6－7－00－6－7－5－00－3－4－00－6－7－5－1－00－3－4－6－7－5－1－00－2－3－4－6－7－5－1－0(3)理想状态下的车辆调度当配送中心使用同类型的配送车时，称为理想状态下的车辆调度。

配送中心：P，记为标号0；可用车辆集合是［qk，k＝1，…，m］，q为载重量；用户[gi

，i＝1，…，n]，gi为用户i的货运量，如果可以混装，则有maxgi

<q；用户i到用户j之间的最短距离记为dij

；具体步骤

:1．计算节约值s(i，j)，令集合S={s(i，j)|s(i，j)>0}；2．对集合S中的元素按从大到小的顺序排序；3．如果集合S=Φ，计算结束，否则对第一个元素s(i，j)，考查对应的(i，j)，是否满足下列条件之一：点i和点j都不在已经构成的线路上；点i和点j中一点是已构成线路的外点，另一点不在线路上；点i和点j分别是已构成的两条线路的外点，其中一个是线路的起点，另一个是线路的终点(0→j→…→0、0→…→i→0，或0→i→…→0、0→…→j→0)。转下步，否则转步骤5；4．考查点i和点j连接后线路上总的货运量Q，如果Q≤q，转下步，否则转步骤6；5．连接点i和点j到同一条线路上；6．令S：S－s(i，j)，转步骤3。例题：现假设有8个用户(标号是1，…，8)，各个用户的货运量是gi(吨)，这些用户由配送中心(标号是0)发出的载货量为8吨的车辆来完成。

用户和用量

用户(i)

1

2

3

4

5

6

7

8货运量(gi)

2

1.5

4.5

3

1.5

42.5

3

配送中心与用户之间的距离

中心0用户140用户1用户26065用户2用户3754075用户3用户49010050100用户4用户52005010050100用户5用户61007575907570用户6用户71601107590759070用户7

用户8801007515010075100100用户8首先，计算节约值：

用户连接的费用节约值(i,j)(5,7)(5,6)(3,5)(5,8)(4,5)(1,5)(6,7)(4,7)(2,5)(2,7)(3,7)(7,8)(4,6)(1,7)S(i,j)270230225205190190190175160145145140115

90(i,j)(2,6)(3,6)(6,8)(1,3)(4,8)(1,6)(2,8)(3,4)(2,3)(2,4)(1,2)(1,4)(1,8)(3,8)S(i,j)

858580757065656560503530205第一步，得出线路0—6—5—7—0，8吨；下面凡是与6、5、7相连的都不连；第二步，得出线路0－

3－1－0，6.5吨；第三步，得出线路0－

4－8－2－0，7.5吨；最后，得到最后的路线安排如下：

0—6—5—7—00—3—1—00—4—8—2—0用户(i)

1

2

3

4

5

6

7

8货运量(gi)

2

1.5

4.5

3

1.5

42.5

3(4)有装载限制的配送路线的制订设配送中心按照一定的分类标准把车辆分成K种，每一种记为K(K=1，…，k)，装载量为qk，数目是xk辆且有如果：单车辆的路线安排

例题：用户和货运量用户

12345678货运量（吨）

1.21.71.51.41.21.61.71.1配送车的类型

4吨

5吨

6吨可以利用的车辆数

50

5

4配送中心、用户之间的距离

中心0用户19用户1用户2145用户2用户321127用户3用户423221710用户4用户53231262725用户5用户6424136312910用户6用户75049443731188用户7

用户85251463929201010用户8发送车辆数

配送车的类型

4吨

5吨

6吨可以利用的车辆数

50

5

4已经分配的车辆数

8

0

0

初始配送计划：用8辆4吨的车给每一个用户送货。0－1－00－2－00－3－00－4－00－5－00－6－00－7－00－8－0用户连接的费用节约值

(i,j)(7,8)(6,8)(6,7)(5,7)(5,6)(5,8)(4,8)(4,7)(4,6)(3,4)(3,7)(3,8)(3,6)(4,5)S(i,j)92848464646446423634343432

30(i,j)(2,3)(3,5)(2,4)(2,5)(2,6)(2,7)(2,8)(1,2)(1,3)(1,4)(1,5)(1,6)(1,7)(1,8)S(i,j)

2826202020202018181010101010第一步：将7、8相连，得线路0－7－8－0，2.8吨，共用7辆4吨车；将6、8相连，得线路0－7－8－6－0，4.4吨，共用1辆5吨车,5辆4吨车；将5、6相连，得线路0－5－7－8－6－0，5.6吨，共用1辆6吨车,4辆4吨车；得出第一条线路：

0－5－7－8－6－0，

5.6吨，该线路可用一辆6吨车配送用户

12345678货运量（吨）

1.21.71.51.41.21.61.71.1计算节约值：用户连接的费用节约值

(i,j)(7,8)(6,8)(6,7)(5,7)(5,6)(5,8)(4,8)(4,7)(4,6)(3,4)(3,7)(3,8)(3,6)(4,5)S(i,j)92848464646446423634343432

30(i,j)(2,3)(3,5)(2,4)(2,5)(2,6)(2,7)(2,8)(1,2)(1,3)(1,4)(1,5)(1,6)(1,7)(1,8)S(i,j)

2826202020202018181010101010第二步：将3、4相连，得线路0－3－4－0，2.9吨，共用1辆6吨车,3辆4吨车将2、3相连，得线路0－2－3－4－0，4.6吨，共用1辆6吨车,1辆5吨车，1辆4吨车将1、2相连，得线路0－1－2－3－4－0，5.8吨，共用2辆6吨车得出第二条线路：

0－1－2－3－4－0，

5.8吨，该线路可用一辆6吨车配送用户

12345678货运量（吨）

1.21.71.51.41.21.61.71.1最终的发送车辆数配送车的类型

4吨

5吨

6吨可以利用的车辆数

50

5

4已经分配的车辆数

0

0

2最终线路如下：0－1－2－3－4－00－5－7－8－6－0表1用户和货运量用户

1234567

8910货运量（吨）0.71.50.80.51.41.50.60.80.50.6练习配送车辆的类型有2吨和4吨两种配送网络图第一步：计算最短距离。

根据配送网络中的已知条件，计算配送中心与客户及其之间的最短距离。第二步：计算节约里程第三步：将节约里程进行分类，按从大到小的顺序排列。第四步：确定配送线路。按节约里程大小顺序，组成线路图。①初始方案：对每一客户分别单独派车送货。初始方案：配送线路10条配送车辆：2t×l0

②修正方案l：按节约里程由大到小的顺序，连接Pl和P2，P1和P10，P2和P3，得修正方案l。修正方案1配送线路：7条配送距离：S1=S0-S1,2--S1,10-S2,3=148-15-13-11=109km装车量:qA=q3+q2+q1+q10=0.8+1.5+0.7+0.6=3.6t配送车辆：2t×6＋4t×1

③修正方案2：在剩余的节约里程中，最大的是S3,4=10和S4,5=10，考虑到车辆的载重量及线路均衡问题，连接P4和P5形成一个新的线路B，得修正方案2。修正方案2配送线路：6条配送距离：S2=S1-S4,5=109-10=99km装车量:qB=q4+q5=0.5+1.4=1.9t配送车辆：2t×5＋4t×1④修正方案3：接下来最大的Sij是S1,9和S5,6。由于此时P1已属于线路A，若将P9并人线路A，车辆会超载，故只将P6点并入线路B，得修正方案3。修正方案3配送线路：5条配送距离：S3=S2-S5,6=99-9=90km装车量:qB’=qB+q6=1.9+1.5=3.4t配送车辆：2t×3＋4t×2修正方案4配送线路：4条配送距离：S4=S3-S6,7=90-5=85km装车量:qB’’=qB’+q7=3.4+0.6=4.0t配送车辆：2t×2＋4t×2

⑤修正方案4：再继续按Sij由大到小排出S9,10、S1,3、S2,10、S2,4、S3,5，由于与其相对应的用户均已包含在已完成的线路里，故不予考虑。把S6,7对应P7点并到线路B中,得修正方案4，⑥最终方案：其次是7,8，考虑到配送距离的平衡和载重量的限制，不将P8并入到线路B中，而是连接P8和P9，组成新的线路C配送线路:3条

配送线路A：P0—P3—P2—Pl—P10—P0使用一辆4t车配送线路B：P0—P4—P5—P6—P7—P0使用一辆4t车配送线路C：P0—P8—P9—P0使用一辆2t车配送距离：S5=S4-S8,9=85-5=80km装车量：qc=q8+q9=0.8+0.5=1.3t配送车辆：2t×l+4t×2习题某面包房每天给固定区域内的五家大零售商店送面包。送货员在面包房装好面包，送到零售商店，再返回面包房。下图给出了该地区的简图，相应的运输时间(以分钟计)如下表。注意由于单行线和绕行，同一路线不同方向的行车时间有些不同(非对称)。a．送货卡车的最佳路线是什么?b．假如装卸时间很重要，该怎样将它们纳入分析之中?c．零售商店3位于人口密集的市区。进出该点的时间可能会增加50％，到其它点的送货时间保持不变。a的解会受这些变化的影响吗?面包房12345至—>012345

002450385520

l22032234518自

247350152160

339271701425

457421816042

52l16572l410答案

求节约值，由s(ij)=ci0

＋c0j–cij

得：s(1，2)=22＋50–32＝40s(4，1)=57＋24–42＝39s(1，3)=22＋38–23＝37s(4，2)=57＋50–17＝89s(1，4)=22＋55–45＝32s(4，3)=57＋38–16＝79s(1，5)=22＋20–18＝24s(4，5)=57＋20–42＝35s(2，1)=47＋24–35＝36s(5，1)=21＋24–16＝29s(2，3)=47＋38–15＝70s(5，2)=21＋50–57＝14s(2，4)=47＋55–21＝81s(5，3)=21＋38–21＝38s(2，5)=47＋20–60＝7s(5，4)=21＋55–41＝35s(3，1)=39＋24–27＝36s(3，2)=39＋50–17＝72s(3，4)=39＋55–14＝80s(3，5)=39＋20–25＝34将节约值由大到小排队答案

s(4,2)s(2,4)s(3,4)s(4,3)s(3,2)s(2,3)s(1,2)s(4,1)s(5,3)s(1,3)8981

80

79

72

70

40

39

3837s(2,1)s(3,1)s(4,5)s(5,4)s(3,5)s(1,4)s(5,1)s(1,5)s(5,2)s(2,5)

36

36

35

35

34

32

29

24

14

70—4—2—00—3—4—2—00—5—3—4—2—00—5—3—4—2—1—0总行程时间为：20+21+14+18+35+22＝130(a)最佳路线：面包房—5—3—4—2—1—面包房旅程需要

130分钟(b)装卸时间可以加到各个点上，再按(a)做。(c)停留点3到其它各点的时间增加50％，其它时间不变。最佳路线的顺序不变，而总旅程时间增加至130+10.5+7＝147.50分钟。答案问题的提出一笔画问题及欧拉图中国邮递员问题五.中国邮路法制定车辆运行路线1.问题的提出中国邮递员问题是我国管梅谷教授于1962年首先研究的，一般定义为邮递员从邮局出发经过他所管辖的街、巷完成信件、报纸的投递任务以后返回邮局，要求邮递员经过各条街道至少一次，如何安排邮递员的行走线路，才能使总路程最短(或费用最少)等。中国邮递员问题，实际上就是物流配送的最短路问题。2.一笔画问题及欧拉图基本概念图G=（V，E）

图、关联、孤立点链和圈的概念

链、圈、连通图

e2

e1

e3

e4

e5

e6

e7

e9

e8

v1

v2

v3

v4

v5

v6

例1点的集合V={v1，v2，v3，v4，v5，v6}

边的集合E={e1，e2，e3，e4，e5，e6，e7，e8，e9}

链

图G中，由两两相邻的点v0，v1，…，vn及其相关联的边e1，e2，…，en构成的点边序列v0，e1，v1，e2，v2，…，vn-1，en，vn称为链。圈

如果链的起点和终点相同，则称该链为圈。连通图

若一个图G的任意两点之间均至少有一条通路连接起来，则称这个图G是一个连通图。链和圈的概念

e2

e1

e3

e4

e5

e6

e7

e9

e8

v1

v2

v3

v4

v5

v6

链：v1，e1，v2，e6，v4，e7，v3圈：v1，e1，v2，e6，v4，e7，v3，e4，v1

e2

e1

e3

e4

e5

e6

e7

e9

e8

v1

v2

v3

v4

v5

v6

欧拉图的基本概念在连通无向图G中，若存在经过每条边恰好一次的一个圈或一条链，就称此圈或链为欧拉圈或欧拉链。欧拉图若图G中含有欧拉圈就称该图为欧拉图。定理

连通无向图G为欧拉图（或含有欧拉圈）的充要条件是它的全部顶点都是偶次顶点。推论连通无向图G有欧拉链的充要条件是它恰含有两个奇次顶点。欧拉链和欧拉圈与一笔画的关系若连通无向图G无奇次顶点，则可由任一点起，一笔画成并回到起点，这就是欧拉圈；若有两个奇次顶点，则由一个奇次顶点起，到另一个奇次顶点终可一笔画成，这就是欧拉链。例2v2e1v6v1v4v5v3v7e6e7e8e2e3e4e53.中国邮递员问题

(1)非欧拉图邮递员问题的引出邮递员问题构成的网络是欧拉图邮递员问题构成的网络时非欧拉图v1→v2→v4→v3→v2→v4→v6→v5→v4→v6→v5→v3→v1总权为12；vl→v2→v3→v2→v4→v5→v6→v4→v3→v5→v3→v1总权为11；

v3vl

v2v4v5v6111111111例3例3

vlv2v3v4v5v6vlv2v3v4v5v6v1→v2→v4→v3→v2→v4→v6→v5→v4→v6→v5→v3→v1vl→v2→v3→v2→v4→v5→v6→v4→v3→v5→v3→v1非欧拉图的邮递员问题可以看作是在一个有奇点的图中，添加一些与原图的边相重复的边，使新图不含奇点，从而得到一个将重复边看成是另一条新边的欧拉图，并且要求重复边的总权最小。[vi，vj]重复边非欧拉图→欧拉图

(2)奇偶点图上作业法奇偶点图上作业法是用图解的方法添加重复边以消除奇次顶点。

总权最小的欧拉图的充要条件在有奇次顶点的图G中，通过加重复边的方法使图不再包含奇次顶点，但原图的每条边最多只能加一条重复边。在图G的每个圈上，重复边之总权不超过该圈各边总权的一半。

作图步骤在图中的街道图中，求邮递员的最优邮递路线。

V8

24V75V2

V9V6V3V4V5V1643344459①确定一个可行方案，使网络各顶点皆为偶次，网络变为赋权欧拉图。

V8

24V75

V2

V9V6V3V4V5V1643344459在任何一个图中，奇点个数必为偶数。把图中的奇点配成对。把这条链的所有边作为重复边加到图中去，新图中必无奇点。

重复边总权为：2W12+W23+W34+2W45+2W56+W67+W78+2W18=51V1V2V3V9V8V7V6V5V424344445569②调整可行方案，使重复边总长度下降。重复边总权下降为21V1V2V3V9V8V7V6V5V424344445569③判断最优方案对G中任一圈C，检查重复边集C1，看是否满足“重复边总权不大于圈上各边总权的一半”的最优性条件。V1V2V3V9V8V7V6V5V424344445569④调整，将重复边与非重复边对换。转第③步。以[v2，v9]，[v9，v4]上的重复边代替[v2，v3]，[v3，v4]上的重复边，使重复边总长度下降为10，小于该圈总长的一半。

V1V2V3V9V8V7V6V5V424344445569V1V2V3V9V8V7V6V5V424344445569V1V2V3V9V8V7V6V5V424344445569V1V2V3V9V8V7V6V5V424344445569在圈v1v8v7v6v9v2

中，以[v1，v2]，[v1，v8]，[v6，v9]上的重复边代替[v7，v8]，[v7，v6]，[v2，v9]上的重复边，使重复边总长度下降为11，小于该圈总长的一半。

V1V2V3V9V8V7V6V5V424344445569重复边总权为：2+5+4+4＝15邮递员行走线路可为：

v1-v2-v3-v4-v9-v4-v5-v6-v9-v6-v7-v8-v9-v2-v1-v8-v1行走路线总长为：5+5+9+4+4+4+4+4+4+3+4+3+6+5+2+2=68练习求出图中的最优邮递员线路。

V3

V5

V2

V1

V4

V6

V7

10

4

9

6

12

12

5

10

7

9

8

9

六.扫描法制定车辆运行路线

扫描法第一个阶段是将停留点的货运量分配给送货车。第二个阶段是安排停留点在路线上的顺序。扫描法的进行步骤将仓库和所有的停留点位置画在地图上或坐标图上。通过仓库位置放置一直尺，直尺指向任何方向均可，然后顺时针或逆时针方向转动直尺，直到直尺交到一个停留点。考虑：累积的装货量是否超过送货车的载重量或载货容积。如是，将最后的停留点排除后将路线确定下来。再从这个被排除的停留点开始继续扫描，从而开始一条新的路线。这样扫描下去，直至全部的停留点都被分配到路线上。对每条运行路线安排停留点顺序，以求运行距离最小化。[例]某公司从其所属的仓库用送货车辆到各客户点提货，然后将客户的货物运回仓库，集中后以更大的批量再进行远程运输。全天的提货量见图，提货量以件为单位。送货车每次可运载1万件。完成一次运行路线一般需一天时间。该公司要求确定：需多少条路线(即多少辆送货车)；每条路线上有哪几个客户点；送货车辆服务有关客户点的顺序。地理区域仓库1,0002,0003,0