运输及配送路线的规划

第八章运输及配送路线的优化教学目的：使学生理解各种运输方式的特点及运输方式选择的原则，掌握运输方式选择的定量分析法，理解存在中间运转的物资调配方法，掌握旅行商问题和中国邮递员问题的解法以及扫描法和节约法。基本要求：1、理解各种运输方式的特点；2、掌握运输方式选择的定量分析法；3、理解存在中间运转的物资调配方法；4、掌握旅行商问题和中国邮递员问题的解法。教学重点：扫描法、节约法教学时数：6学时第一节运输方式的选择口运输方式选择的原则当同时存在多种运输方式可供选择的情况下，就需要进行选优抉择。通常根据各种运输方式的经济特性和服务特征来选择合适的运输方式，即主要依据运输成本、运输速度、可靠性、安全性等指标进行判断和选择。安全性原则——首要的原则及时性原则准确性原则经济性原则——主要原则货物运输的六大方式：根据运输工具的不同，可分为：水路、公路、铁路、航空、管道和多式联运等运输形式。在各种运输方式中，如何选择适当的运输方式是物流合理化的重要问题。可以选择一种运输方式也可以选择使用联运的方式。运输方式的选择，需要根据运输环境、运输服务的目标要求，采取定性分析与定量分析的方法进行考虑。口运输方式选择的定性分析法定性分析法主要是依据完成运输任务可用的各种运输方式的运营特点及主要功能、货物的特性以及货主的要求等因素对运输方式进行直观选择的方法。单一运输方式的选择单一运输方式的选择，就是选择一种运输方式提供运输服务。公路、铁路、水路、航空和管道五种基本运输方式各有自身的优点与不足，可以根据五种基本运输方式的优势、特点，结合运输需求进行恰当的选择。一般要考虑的因素是：

•运费的高低•运输时间的长短•频度——运、配送次数•运输能力——运量的大小•货物的安全性——运输途中的破损或污染等•到货时间的准确性各种运输方式的比较运输方式铁路运输公路运输航空运输水路运输运输速度较快较快快慢运输距离长较短长较长可靠性高较高高较低运输量较大较小小大灵活程度较高高较低低自然条件影响少较少较多多适运货物大宗货物量少、日用品、短途急用、高附加值物品大宗货物多式联运的选择多式联运的选择，就是选择两种以上的运输方式联合起来提供运输服务。在实际运输中，一般只有铁路与公路联运、公路或铁路与水路联运、航空与公路联运得到较为广泛的应用。铁路与公路联运，即公铁联运，又称为驮背运输，是指在铁路平板车上载运卡车拖车进行的长距离运输。公路或铁路与水路联运，又称为鱼背运输，是指将卡车拖车、火车车厢或集装箱转载驳船上或大型船舶上进行的长距离运输。鱼背运输最大的优势是运量大、运费低，所以在国际多式联运中被广泛采用。航空与公路联运也是被广泛采用的运输方式，这种将航空运输快捷、公路运输灵活方便的多种优势融合在一起提供的运输服务，能以最快的方式实现长距离“门到门”的货物运输。□运输方式选择的定量分析法运输方式选择的定量方法有综合评价法、总成本分析法、考虑竞争因素的方法等多种方法，应用时可根据实际情况选择其中的一种进行定量分析。主要介绍总成本分析法运输方式与运输费用的关系总成本分析法□以年总成本最低为原则来选择合适的运输方式的分析方法。总成本=运输成本+库存成本

其中：运输成本二运输量X运费率（单位运价）库存成本运输库存成本二运输量X单位存货成本X运输时间存储库存成本=平均存货量X单位存货成本总成本分析法实例例8-1某公司欲将产品从坐落位置A的工厂运往坐落位置B的公司自有的仓库，年运量D为70万件，每件产品的价格C为30元，每年的存货成本I为产品价格的30％。公司希望选择使总成本最小的运输方式。据估计，运输时间每减少一天，平均库存水平可以减少1％。各种运输服务的有关参数如表8-1所示，试确定最优的运输方式。表8-1各种运输方式的基本参数运输方式铁路

驮背

公路

航空运输费率R（元/件）0.10.15运输方式铁路

驮背

公路

航空运输费率R（元/件）0.10.150.21.4运输时间T（天）2114年运送批次（次）10202040平均存货量Q/210000050000X0.9350000X0.8425000X0.81表8-2各种运输方式的成本计算结果成本类型铁路运输驮背运输公路运输航空运输成本类型铁路运输驮背运输公路运输航空运输运输成本70000105000140000980000运输成本70000105000140000980000在途成本3624662416448630134521在途成本3624662416448630134521工厂存货900000418500378000182250工厂存货900000418500378000182250仓库存货903000420593380520190755仓库存货903000420593380520190755总成本223546611857379848211387526总成本223546611857379848211387526经过比较可知，总成本最低的是公路运输方式，其次是驮背运输方式。按照总成本最低的原则，应该选择公路运输方式。例8-2某制造商分别向两个供应商购买了4000个配件，每个配件单价150元。目前这4000个配件是由两个供应商平均提供的，如供应商缩短运达时间，则可以多得到交易份额，每缩短一天，可从总交易量中多得5%的份额，即200个配件。供应商从每个配件可赚得占配件价格（不包括运输费用）20%的利润。于是，供应商A考虑如果将运输方式从铁路转到卡车运输或航空运输可能会增加利润。各种运输方式的运费率和运达时间如下表所示：运输方式铁路运费率运输方式铁路运费率（元/件）2.25运达时间（天）7卡车航空卡车航空10.00试问：供应商A该如何决策？求解：显然，供应商A只能根据他可能获得的潜在利润来对运输方式进行选择决策。下表8-3所示是供应商A使用不同的运输方式可能获得的预期利润。

、一上人.》，_lx运输方式铁路卡车航空配件销售量、一上人.》，_lx运输方式铁路卡车航空配件销售量/件200026003000毛利/元600007800090000运输成本/元45001430030000净利润/元555006370060000如果制造商对能提供更好运输服务的供应商给予更多份额的交易的承诺实现，则供应商A应当选择卡车运输。当然，与此同时供应商A还要密切注意供应商B可能做出的竞争反应行为。第二节物资运输调配决策物资运输调配决策是指在多个供应地和多个需求地之间如何合理调配物资，以实现在满足需求前提下的总运输成本最低的目的。这类决策根据起讫点之间是否存在中间转运分两种情况进行讨论一、多起讫点的直达运输分为:产销平衡的运输问题产销不平衡的运输问题其解法是：表上作业法运输问题实例练习：有三个产地A，A和A，生产同一种物品，使用者为B，B和B，各产地到各使用者的单位1运价2见下3表所示。这三个使用者的需求量1分别2为130、4和6个单位。由于销售需要和客观条件的限制,，产地至少要发出6个单位的产品，它最多只能生产11个单位的产品；必须发出7个单位的产品； 至少要发出4个单位的产品。根据上述条件用表上作业法求该运输问题3的最优运输方案。各产地到各使用者的单位运价表：二、存在中间转运的物资调配这类问题又称为“转运问题”（一）问题描述m供应地中转站需求地m供应地中转站需求地二）数学模型minZ=Y区CX+]E^CXkikiijijk=1i=1 i=1j=1迟X<ak=1,2,...,fkiki=1YX<ti=1,2,...,mkiik=1YX=YXi=1,2,...,mki ijk=1 j=1jk=1,2,...,f;i=1,2,...,m;j=1,2,...,n迟X>bj=jk=1,2,...,f;i=1,2,...,m;j=1,2,...,niji=1X>0,X>0ki ij（三）求解方法口思路:将转运问题化为无转运问题，再用表上作业法求解口1.首先根据具体问题求出最大可能中转量Q口2.纯转运站可视为输出量和输入量均为Q的一个产地和销地口3.兼中转站的产地Ai视为一个输入量Q的销地及一个输出量为ai+Q的产地口4.兼中转站的销地Bj视为一个输入量bj+Q的销地及一个输出量为Q的产地转运问题输入、输出、中转量图示

*®+Q*®+Qbj+Q Bj Q转运问题：在原运输问题上增加若干转运站。运输方式有：产地T转运站、转运站T销地、产地T产地、产地T销地、销地T转运站、销地T产地等。转运问题实例例8-3某公司有两个工厂生产变压器。一个工厂在A市，另一个工厂在B市，它们每天的生产能力分别为150和200。变压器通过汽车运到需求点C市和D市。C市和D市的需求量均为130。公司还需要两个中间转运站E市和F市进行整合运输，各点间单位运输费用如下表所示。试确定从工厂到需求点的最优路线。项目ABEFCDA013461214B130761312E470388F663078C121387017D141288170求解：该问题可分为两个阶段求解：第一阶段：将实际的转运问题转化为标准的运输问题。经分析可知，该问题的最大可能中转量为350。根据转运问题的性质，确定A、B产地的供应量分别为500(150+350)、550(200+350)；E、F中转地的中转量都是350；C、D需求地的需求量均为480(130+350)。建立新的产销平衡表如下：项目1313C121381412121314120 71717虚拟供应量500550350350350350需求量350350350350项目1313C121381412121314120 71717虚拟供应量500550350350350350需求量35035035035048048090第二阶段：运用求解产销平衡的运输问题的表上作业法求解。例8-4腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产450台，广州分厂每月生产600台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如下图，单位是百元。问应该如何调运仪器，可使总运输费用最低？1-广州、2-大连、3-上海、4-天津、5-南京、6-济南、7-南昌、8-青岛解：设xij为从i到j的运输量，可得到如下列运输问题模型：数学模型：Minf=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48s.t. x13+x14W600（广州分厂供应量限制）x23+x24+x28W450 （大连分厂供应量限制）xL3+x23 = x35 + x36+ x37 + x38 （上海销售公司，转运站）xL4+x24 = x45 + x46+ x47 + x48 （天津销售公司，转运站）x35+x45=200（南京的销量）x36+x46=150（济南的销量）x37+x47=350（南昌的销量）x38+x48+x28=300（青岛的销量）xij三0,i,j=1,2,3,4,5,6,7,8

用“管理运筹学”:软件求彳得结果：x13=550x14=0x23=0x24=150x28=300；x35=200x36=0x37=350x38=0x45=0x46=150x47=0x48=0例8-5某公司有Al、A2、A3三个分厂生产某种物质，分别供应Bl、B2、B3、B4四个地区的销售公司销售。有关数据如下表所示。试求总费用为最少的调运方案。B2B3B4产量A3113107A219284A3741059销量365620假设：每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运；运往各销地的物资可以先运给其中几个销地，再转运给其他销地；除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。各产地、销地和中转地之间的运价如下表：

解：Stepl:把此转运问题转化为一般运输问题：把所有产地、销地、转运站都同时看作产地和销地；运输表中不可能运输处的运费取作M,自身对自身的运费为0；3.产量及销量可定为：中转站：产销量均为20，产地：原产量+20，销地：销量+20。20为最大可能中转量扩大的运输问题产销平衡表：A1A2A3T1T2T3T4B1B2B3B4A10132143311310A；10M35M21928A33M01M2374105T12310132286t215M1011457t34M23102184T432321201M6B137110142b21148M1021b3310224203105462130销量2020202020202023262526Step2:运用表上作业法求解5-172411142B1-2618244527T才311322846-235-21321433113101234BBBB10105-172411142B1-2618244527T才311322846-235-21321433113101234BBBB1010第三节单一车辆配送路线的优化主要是指对单一运输车辆从起点到终点间的最短行车路线进行优化。优化的目标可以是行车时间最短、距离最短或运输费用最小，一般统称为最短路径问题。单一车辆的配送路线优化可分为两种类型：起讫点不同的单一路线优化和起讫点重合的单一路线优化。一、起讫点不同的单一路线优化主要方法有：动态规划法、Dijkstra法、逐次逼近法等不同的求解方法。本节主要介绍动态规划法。动态规划（DynamicProgramming）动态规划（DP）是运筹学的一个分支，是解决多阶段决策过程最优化的一种数学方法。由美国数学家贝尔曼（Ballman）等人在20世纪50年代提出。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题。动态规划是求解某类问题的一种方法，是考察问题的一种途径，但不是一种特殊算法。学习动态规划就要首先了解多阶段决策问题多阶段决策问题多阶段决策问题和我们前面遇到的决策问题不同，它是和时间有关的。与时间有关的活动过程称为动态过程，其优化方法称为动态规划。而与时间无关的活动过程称为静态过程，相应的的优化方法称为静态规划。所谓多阶段决策问题是：把一个问题看作是一个前后关联具有链状结构的多阶段过程，也称为序贯决策过程。如下图所示：1.最短路径问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或运费），试求从A点到G点的最短距离（总运输费用最小）。1234562、机器负荷的分配问题设有某种机器可以在高、低两种不同的负荷下进行生产。若在高负荷下进行生产时，产品的产量g和投入生产的机器数量X的关系为g=g(x)，这时，机器的年完好率为a；若在低负荷下进行生产时，产品的产量h和投入生产的机器数量x的关系为h=h(x),相应的机器年完好率为b。假设开始生产时完好的机器数量为Q，要求制订一个五年的生产计划，合理分配机器负荷，使总收益达到最高。3、资源分配问题设有数量为a的资源，计划分配给n个项目。设xi(i=l,2, n为分配给第i个项目的资源量，gi(xi)为第i个项目得到数量为xi的资源后可提供的收益，问如何分配资源a，可使总收益为最高？maxf=Xg(x)iii=1厶x=a<i=1X>0,i=1,2,...,ni4、背包问题有一个徒步旅行者，其可携带物品重量的限度为A公斤，设有n种物品可供他选择装入包中。已知每种物品的重量及使用价值(作用)，问此人应如何选择携带的物品，才能使所起作用(使用价值)最大？物品n12… j …重量(公斤/件)anala2… aj …每件使用价值cnc1c2… cj …设决策变量x.表示旅行者携带第/件物品的情况令_ri当携带第/件物品令x._|o否则动态规划的基本概念（1） 阶段（stage） 阶段变量imaxZ丄cx..._1工ax<A..._1x_0或1(j_1・2.・・・.n).（2） 状态（State）状态变量si、可达状态集合Si■最短路问题中，各个阶段结点就是状态■机器负荷分配问题中，各阶段的完好机器数是状态■物资分配问题中，分配给前i个项目的物资量是状态（3） 决策（decision）决策变量xi（si）、允许决策集合Di（si）机器负荷分配问题中，分配高（低）负荷下的机器数最短路问题中，走哪条路物资分配问题中，分配给每个项目的物资量（4） 策略（Policy）各阶段的决策组成的一个决策序列称为一个策略，记为：从阶段i开始的过程，称为i子过程，它包含阶段i,阶段i+1,…，阶段n。i子过程的决策序列称为i子策略，记为p_1x,x，…,xi_1,2,…,n一1iii+1 n（5） 状态转移方程由某一阶段的一个状态到下一阶段的另一状态的演变称为状态转移。描述状态转移规律的方程称为状态转移方程。记为si+1=gi（si,xi），gi称为状态转移函数。（6） 阶段指标、指标函数、最优指标函数阶段指标（阶段收益），衡量每一阶段决策优劣的数量指标。动态规划的基本方程,x)+f动态规划的基本方程,x)+f*(s)}i i+1i+1逆序解法：*(s)_optiixifn+1(Sn+1)=0顺序解法： /尸f*(s)_optViii_n,n一1,・・・,1(s,x)+f*(sii i一1i一1Ji_1,2,…,n占fo(so)=0动态规划的求解步骤用动态规划求解最短路径问题（1）确定问题的阶段;（2）确定状态变量■用Si表示第i阶段的状态变量及其值（3） 确定决策变量■用Xi表示第i阶段的决策变量，并以xi*表示该阶段的最优决策（4） 正确写出状态转移方程si-1=g（si,xi）逆序求解 si+1=g（si,xi）顺序求解（5） 正确写出指标函数和递推关系式（6）用正向递推算法或逆向递推算法求出每阶段的最优指标值及相应的最优策略。最后求得全过程的最优策略。用动态规划求解最短路径问题例8-6、从A地到E地要铺设一条煤气管道，其中需经过三级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？解：整个计算过程分四个阶段，从最后一个阶段开始。严2）=2C至【」D有6严2）=2C至【」D有6条路线。显然有f(D)=5;41第三阶段(C-D):考虑经过C的两条路线1TOC\o"1-5"\h\z.[d(C,D)+f(D)[ .[3+5[ 8Q/ [d(C,D)+f(D)J [9+2j1 2 4 2(最短路线为 ctDTE考虑经过C的两条路线1 12.\d(C,D)+f(D)] .[6+f(C)=mm< 2i4i>=mm〈 >=732 [d(C,D)+f(D)J [5+2j242

（最短路线为ctDTE ）考虑经过C的两条路线3.\d(C,D)+f(D)[ .[8+5[Q3丿[d(C,D)+f(D)J[10+2J2 4 2最短路线为CTDTE第二阶段（Bf。：B到C有9条路线。考虑经过B的3条路线1I"(B1I"(B1，C1)+gf(B)=min21d(B1,C2)+f3(C2)[d(B1,C3)+f3(C3)[12+8、>=min<14+7>=20

[10+12最短路线为 BTCTDTEd(B,C)+f(C)2 1 4 1最短路线为 BTCTDTEd(B,C)+f(C)2 1 4 16+8、f(B)=min22d(B,C)+f(C)2 2 4 2=min10+7>d(B,C)+f(C)2 3 4 34+12考虑经过B的3条路线1 12最短路线为=14BTCTDTE211考虑经过B3的3条路线I[d(B3,C1)+f3(C1)f(B)=min\d(B,C)+f(C)2 3 3 2 3 2[Id(B,C)+f(C)3 3 3 323、13+8、>=mim12+7>11+12=19最短路线为 BTCTDTE第一阶段（AfB）：3A到B有3条路线。I[d(A,B1)I[d(A,B1)+f2(B1)f(A)=min<d(A,B2)+f2(B2)[d(A,B3)+f2(B3)[2+20、>=min<5+14>=19

[1+19_最短路线为（最短距离为最短路线为（最短距离为19）ATBTCTDTE211口用Dijkstra标号算法求最短路问题的实例略自己在课下练习二、起讫点重合的单一路线优化口起讫点重合的线路优化主要是指从某点出发访问一定数量顾客后又回到原来出发点的线路优化问题。现实生活中存在着许多类似的问题，如配送车辆送

货、邮递员送报、送奶工送牛奶、垃圾车辆收集垃圾等。（一）旅行售货员问题（TravelingSalesmanProblem）问题描述某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程（或总旅费）最小。TSP也可用网络图或矩阵描述：Cij02231<452231Cij02231<45223101827180273838数学模型TSP除了可以用文字叙述和网络图来描述以外，还可以使用模型化的形式来表达，即用整数规划模型来表达。记d为由城市i到j的距离（费用、时间等）， [1由城市i到城市jij x=2并将决策变量取作x，i,j=1,2,...,n。 ij[o否则ijijiji=ijiji=1j=1工x=1j=1,2,.・・,n，i丰jij£x=1 i=1,2,...,n，j丰iijj=1s.t.2x+x<2 i丰s.t.2ijjix+x+x<3 i丰j丰li丰i丰j丰l丰...丰px+x+...+x<n-1，\ijjl pix=0或1ij上述0-1规划模型的约束条件的含义：第一组约束表示：每个城市必去，且仅去一次第二组约束表示：每个城市必离，且仅离一次第三组约束表示：不允许有两个城市间的循环第四组约束表示：不允许有三个城市间的循环以下诸式含义与此类同。求解方法口TSP是一个典型的NP—Hard问题，对于大规模的线路优化问题，无法获得最优解，只有通过启发式算法获得近优解。下面介绍两种比较简单的启发式算法：贪婪算法(最近邻点法)Stepl:首先选择离出发点最近的点；Step2:再从剩下的点中选距离已选择的点最近的点；Step3:如果所有的点都被选了，则停止；否则返回Step2。例8-7在下图中，从配送中心A出发，送货至胆、C、D三个客户需求站。任意两点间的距离已知(如图中所示)，求最佳配送路径。最佳配送路线为：A——B——C——D——A总路程=22+l8+38+45=l23最近邻点法极为直观与简单，但结果的满意度往往较差。最近插值法(NearestInsertion)口最近插值法是Rosenkrantz和Stearns等人在1977年提出的一种用于解决TSP问题的算法，它比上面的最近邻点法复杂，但是可以得至相对比较满意的解。最近插值法的步骤：Step1.找至距离起点最近的节点，形成一个子回路。Step2.在剩下的节点中，寻找一个距离回路中某一节点最近的节点VStep3.在子回路中找到一条边(i,,j),使得j—cj 最小，然后将节点Vk插入到节点V,V之间，用两条边(i,k)、(k，j)代替原来的边(i,j)。Step4.重复Step2和Step3，直到所有的节点都加入子回路中。用最近插值法求解例8-7，并分析所得解的满意性。练习一一求解下列权系数矩阵所表示的TSP23456v-0101v2100vC=365ijv4820v5715v6151668715「520151601478140412740681260解法1v1v2vC=3ijv4v5v6vvvvvv12345601068715100520151665014788201404127157406151681260---v-2--v5----v4---最近邻点法-v6v---v13总路程=6+5+15+4+12+15=57--v1解法2——最近插值法v---v---v v v v v1236541总路程=10+5+8+6+4+8=41案例：“最佳灾情巡视路线”今年（1998年）夏天某县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。2）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=l小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线。itj.ist217<34A★12ewWU35tlAH县界I\/sj3\ASitj.ist217<34A★12ewWU35tlAH县界I\/sj3\AS5"厂辱\\叭仏/7；fl1 X公路边的数字为该路段的公里数问题分析：本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线。将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点0出发，行遍所有顶点至少一次再回到点0,使得总权（路程或时间）最小。本题是旅行售货员问题的延伸一多旅行售货员问题。本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的回路。

如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题。（二）中国邮递员问题（ChinesePostmanProblem）中国邮递员问题（CPP）是由中国著名运筹学家管梅谷教授于1962年首先提出并作了深入研究，其成果得到国际、国内运筹学界极高的赞誉，所以被称为“中国邮递员问题”或“中国邮路问题”。问题描述CPP可以这样叙述：一名邮递员负责投递某个辖区的邮件。他从邮局出发，经过投递辖区内每条街道至少一次，最后返回邮局，问：如何安排一条最短的投递路线？用图论的语言可描述为：给定一个连通图G,每条边都有一个非负权数。现要求一个圈C经G的每边至少一次，且使C的权和最小。CPP求解的基本思路为了理解CPP求解方法的思路，需要回顾一下欧拉（Euler）解决“哥尼斯堡七桥”问题的方法：一笔画问题。该问题涉及到一些图论的基本概念：顶点的度（次）、奇点、偶点、链、圈、欧拉圈、欧拉图等CPP求解基本思路：如果在邮递员负责的辖区里，街道图中没有奇顶点，则存在欧拉圈。邮递员从邮局出发，经过每条街道一次，且仅一次，最后回到邮局。此时的投递路线最短，即最佳投递路线。如果街道图中有奇顶点，就必须在某些街道上重复走一次或多次。重复的街道必与奇顶点相连。求解方法——奇偶点图上作业法我们将邮递员管辖的街道图视为无向图G=（V，E），若G没有奇顶点，贝临是一个欧拉图，G含的欧拉圈即为所求。若图中有奇点，则按下述步骤求解：第一步：把图G的奇顶点两两配对，并将每对奇顶点间的通路上的各边作为重复边添加到图G上，得到的新图全部顶点都是偶顶点。第二步：如果某边上的重复边多于一条，贝可从中删去偶数条，使每边的重复边最多只有一条。第三步：检查图G中的每个圈：若所有圈的重复边的总长度都不大于该圈长度的一半时，贝得到最优方案。否贝，若有一个圈，该圈的重复边的总长度大于该圈长度的一半，就将该圈的原有重复边删去，给该圈原来没有重复边的各边都加上一条重复边。重复这个过程，直到没有这种圈为止。求解下图所示网络的中国邮路问题（1） 确定初始方案（2） 判断方案的最优性（3） 调整可行方案（4） 继续调整方案奇偶点图上作业法在实际运用中已作出许多贡献。它不仅可以提高邮递员的工作效率，而且对于街道清扫路线、纺织工看车路线、仓库员巡视货物路线等类似问题的研究，都有实际意义。第四节多车辆配送路线的优化口多车辆路径问题（VehicleRoutingProblem）VRP最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。由此定义不难看出，旅行商问题（TSP）是VRP的特例。VRP的特点：口属于节点服务的网络组合最优化问题口除了场站（物流中心）节点外，其余节点恰由一辆车服务一次口多车辆路线，且车辆具有容量限制口各车辆路线所服务的顾客需求总和不得超过车辆容量口求解复杂度属于NP-hard，大规模问题难以求得最优解，实践中多采取“启发