送货路线设计问题数学建模优化

1、送货路线设计问题现今社会网络越来越普及，网购已成为一种常见的消费方式，随之 物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送 达，而且他们往往一人送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在图1中的0点，一送货员需将货物送至 城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图 见图1 ,各点连通信息见表3 ,假定送货员只能沿这些连通线路行 走，而不能走其它任何路线。各件货物的相关信息见表1 , 50个位 置点的坐标见表2 o假定送货员最大载重50公斤，所带货物最大体积1立方米。送 货员的平均速度为24公里/小时。假定每件货物交接花费3分 钟，为简化起见，同一地

2、点有多件货物也简单按照每件3分钟交接计 算。现在送货员要将100件货物送到50个地点。请完成以下问题。1 .若将130号货物送到指定地点并返回。设计最快完成路线与方 式。给出结果。要求标出送货线路。2 .假定该送货员从早上8点上班开始送货，要将广30号货物的送达 时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货 线路。3 .若不需要考虑所有货物送达时间限制（包括前30件货物），现 在要将100件货物全部送到指定地点并返回。设计最快完成路线与方 式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体 积限制，送货员可中途返回取货。可不考虑中午休息时间以上各问尽可能给出模型与算法

3、图1快递公司送货地点示意图0点为快递公司地点，0点坐标（11000, 8250）,单位：米表1各货物号信息表货物号送达地点重量（公斤）体积（立方米）不超过时间1132. 500.03169： 002180. 500. 03549： 003311. 180. 02409： 304261.560. 035012： 005212. 150. 030512： 006141.720.010012： 007171.380.010912： 008231.400. 042612： 009320. 700.048112： 0010381.330.021910： 1511451. 100. 02879： 3012

4、430. 950. 022810： 1513392. 560. 059512：0014452.280.03019：3015422. 850.019010：1516431.700. 078210：1517320. 250.041212：0018361.790.018412：0019272. 450.044512：0020242. 930. 04209：0021310. 800.01089：3022272. 250.001812：0023261.570.021012：0024342. 800.01039：3025401. 140.01559：3026450. 680. 03829：3027491.

5、350. 014410：1528320. 520. 002012：0029232.910. 048712：0030161.200. 042912：003111.260. 02503221. 150. 05013331.630. 04833441.230. 00063551.410. 03873660. 540. 00673770. 700.01293880. 760. 03463992. 140. 008740101.070.012441111.370.051042122. 390. 042843130.990. 004844141.660. 049145150.450. 020946162.

6、040. 009847171.950. 032448182. 120. 055449193. 870.026250202.010. 032451211.380.041952220. 390. 000153231.660. 050254241. 210. 053455252.410.001256261.260. 005957270. 420. 022458281.720. 058059291. 340. 037260300. 060. 040261310. 600. 027462322. 190. 050363331.890. 049464341.810. 032565351.000. 0055

7、66361. 240.017767372.510.036168382. 040.011069391.070.044070400. 490. 032971410. 510. 009472421.380. 045573431. 310.012174441.260. 000575450.980.041376461.350. 024177472. 120. 023078480. 540. 054279491. 010. 056680501. 120. 028481250. 790.001182462. 120. 049283322. 770. 003484232. 290. 005485200.210

8、. 049086251.290. 008887191. 120. 024988410. 900. 003889462. 380. 043490371.420. 002091321. 010. 030092332.510.013393361. 170. 002094381.820.030895170. 330. 034596110. 300.017297154. 430. 053698120. 240. 005699101. 380.017510071. 980. 0493表2 50个位置点的坐标位置点X坐标（米）Y坐标（米）19185500214455603727057043735670526

9、209956100801435710025228087160252591384526801011935305011785035451265854185137630520014134055325152125597516153657045171416573851888258075195855816520780835521127708560222200883523147659055247790933025443595252610860963527103851050028565976529258098653015659955319395101003214835103653312501090034728

10、01106535153051137536123901141537641011510381391511610399510120504083451230041493013650421326514145431418014215443030150604510915142354623301450047773514550488851488049115751516050801015325表3相互到达信息序号位置点1位置点21132183220424538634742851595210611171812711381214914159101610181710718111219121320122521121522

11、1318656 463626 1g595005 756555453525 1g494 004 74 645444 3424 i舍393COOO3 6353 43332OO292 002 72 524234 i舍台393 00373636353433333232CaO292OO27252525242322toLOLOgs001o15i5co004445342736舍274 5300当20046233534264 i2002233329o4 i311362622243232325222131001664137674146684243694249704338714448724450734550744

12、542754648764740774844784950794942805040810188202183026快递公司送货策略摘要：本文是关于快递公司送货策略的优化设计问题，即在给定送货地点和给定设计规范的条件下， 确定所需业务员人数，每个业务员的运行线路，总的运行公里数，以及费用最省的策略。本文 主要从最短路经和费用最省两个角度解决该问题，建立了两个数据模型。模型一：利用“图” 的知识，将送货点抽象为“图”中是顶点，由于街道和坐标轴平行，即任意两顶点之间都有 路。在此模型中，将两点之间的路线权值赋为这两点横纵坐标之 和。如A (xl, yl ) , B(x2, y2)两点，则权值为D=|x2-

13、xl| + |y2-yl|。并利用计算机程序对以上结果进行了校核。 模型二：根据题意，建立动态规划的数学模型。然后用动态规划的知识求得最优化结果。根据 所建立的两个数学模型，对满足设计要求的送货策略和费用最省策略进行了模拟，在有标尺的 坐标系中得到了能够反映运送最佳路线的模拟图。最后，对设计规范的合理性进行了充分和必 要的论证。二关键词： 快递公司送货最优化图模型多目标动态规划TSP模型三问题重述: 在快递公司送货策略中，确定业务员人数和各自的行走路线是本题的关键。这个问题可以描 述 为：一中心仓库（或配送调度中心）拥有最大负重为25kg的业务员m人，负责对30个客户 进行货物分送工作，客户i

14、的快件量为已知，求满足需求的路程最短的人员行驶路径，且使用尽 量少的人数，并满足以下条件：1）每条送快件的路径上各个客户的需求量之和不超过个人最大负重。2）每个客户的需求必须满足，且只能由一个人送货.3 ）每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度 为 25km/h 。4 ）为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克。表一为题中所给的数据：表最大载重量25kg重载时速20km/h途中的平均速度25km/h重载酬金3 元 /km*kg业务员工作时间上限6h空载时速30km/h每个送货点停留时间lOmin空载酬金2 元 /k

15、m备注1、快件一律用重量来衡量2、假定街道方向均平行于坐标轴处于实际情况的考虑，本研究中对人的最大行程不加限制.本论文试图从最优化的角度，建立起满 足设计要求的送货的数学模型，借助于计算机的高速运算与逻辑判断能力，求出满足题意要求的 结果。四问题分析：从公司总部配出一个人，到任意未配送的送货点，然后将这个人配到最近的未服务的送货点范围 之内的邻居，并使送货时间小于6小时，各送货点总重量不超过25kg o继续上述指派，直到各 点总重量超过25kg ,或者送货时间大于6小时。最后业务员返回总部，记录得到的可行行程（即 路线）。对另一个业务员重复上述安排，直到没有未服务的送货点。对得到的可行的行程安

16、排解中 的每一条路径，求解一个旅行商问题，决定访问指派给每一条行程的业 务员的顺序，最小化运输 总距离。得到可行解的行程安排解后退出。根据题意的要求，每个人的工作时间不超过6小时，且必须从早上9点钟开始派送，到当 天17点之前（即在8小时之内）派送完毕。且 .5kg 8 ,故至少需要8条路线。表25kg 二列出了题中任意两配送点间的距离。表二：任意两点间的距离矩阵因为距离是对称的，即从送货点i到送货点j的距离等于从j到i的距离。记作：dij.表三给出了客户的需求，为了完成送快递的任务，每个人在工作时间范围内，可以承 担两条 甚至更多的线路。表中给出了送货点序号，送货点编号，快件量 T ,以及送

17、货点的直 角坐标。表三序号送货点快件量T坐标 (km )序号送货点快件量T坐标(km )XyXY1183216163. 5216228.21517175.86183365418187.51117445.54719197.815125630820153.4199654.531121326.2225777.27922226.8210882.39623232.4279991.410224247.6151910106.514025259.6151411114. 11732626102017121212. 7146272712211313135.812928286.02242014143.8101229

18、298. 1251615201. 671-13030-1. 22818五模型假设：（1 ）街道方向均平行于坐标轴，且在该前提下，业务员可以任意选择路线。（2 ）无塞车现象，即业务员送快递途中不受任何外界因素影响，且业务员的休息时间不包 括在最 大工作时间6个小时内。（3 ）业务员人数不限制。（4 ）每个业务员的路线一旦确定，便不再更改。（5 ）每个业务员送快递是独立的，每人之间互不影响。（6 ）业务员到某送货点后必须把该送货点的快件送完。（7 ）每个业务员每天的工作时间不超过6个小时。（8 ）业务员回到快递公司后停留一个小时。六主要符号说明：Ti ：序号为i的送货点的快件重量（xi , yi

19、）序号为i的送货点的坐标M重：业务员送货总重载费用M空：业务员送货总空载费用M总：业务员送货总费用N：业务员送货的总次数m ：业务员人数mj ：第j个业务员送货的次数1,业务员在序号为i的送货点送快件0,业务员在序号为i的送货点没有送快件1,第k条路线选择序号为i的送货点是最远点0,第k条路线选择序号为i的送货点不是最远点七模型建立与求解：7.1问题一模型本模型考虑用多目标动态规划求解。由于问题一中只要求给出一个合理的方案，且未涉及到 业务 员工资问题，故只要满足条件一一业务员的工作时间上限是6个小时以及每条路线的最大载重量不 大于25kg即可，本模型中追加两个目标一一路程最短和人员最少。可以

20、通过以下两种方法实现：（1）每一个行程的第一个送货点是距离总部最近的未服务的送货点。用这种 方法，即可得到一组运行路线，总的运行公里数，以及总费用。（2 ）每一个行程的第一个送货点 是距离总部最远的未服务的送货点。然后以该点为基准，选择距它最近的点，加上约束条件，也可 得到一组数据。然后比较两组结果，通过函数拟合即可得到最优化结果。本模型中以满足需求的路程最短的人员行驶路径，且使用尽量少的人数，即N 30min (2*bklili*(xi+yi)且 nunm约束条件为:6 i iai)mj 2(X1时间约束：载重量约束:ji yi ) Ti * ai 25方法一：每一个行程的第一个送货点是距离

21、总部最近的未服务的送货点。开始找离原该点最近的点V,且该点的访问标志设为被访问，该点快递重 量为W ,输出该点。找点V最近的点，快递重量为wl ,且wl+w<25 ,当其不成立时找次 远点。(3) 010 12 8 9 0找到符合条件的点，且不 止一个时选择快递重量最 重的那个点，访问标志设 为被反问，并输出该点， 赋值给V,且w=w+wl ；第一条行程中访问了节点0-1-3-4-5-0，是因为1距离原点最近，因此由1出发,3是距离1点最近的点，而且两处快件量之和为14kg，小于每个人最大负重量，可以继续指配。接着， 4是距离3最近的点，而且三处快件量之和为19. 5kg ,仍小于25k

22、g,还可以继续指配。在剩 下的未服务送货点中，5距离4最近（其实距离4最近的点有2 , 5 , 6 , 7四个点，然后 考虑该点需求的快件量，将其从大到小依次排列，快件量需求大者优先，但超过25kg上限的点 舍去。这里2 , 7被舍去，故选择了 5 ）总快件量之和为24kg o再继续扩充，发现就会超 出“ 25kg ”这个上限，因此选择返回，所以0T-3-4-5就为第一条路线所含有的送货点。用该算法得到的各路线为:(1) 01 3 4 5 0(2)6 7 13 0(4)16172014 1523(5) 01122(6) 02726321900(7) 01824250(8) 029 28 30

23、0现在0-1-3-4-5这四个送货点之间的最优访问路径安排就是一个典型的单回路问题。可以通 过单回路运输模型-TSP模型求解。一般而言，比较简单的启发式算法求解TSP模型求解有 最邻近法和最近插入法两种。由RosenkrantzStearns等人在1977年提出的最近插入法，能够比最近邻点法，取得更满意的解。由于0-1-3-0已经先构成了一个子回路，现在 要将节点4插 入，但是客户4有三个位置可以插入，现在分析将客户4插入到哪里比较合 适：1 .插入到（0, 1）间，C 总= 7+4+5+1+4+9=30。2 .插入到（1, 3）间，C 总=5+6+4+9=24。3 .插入到（3, 0）间，C

24、 总=5+4+4+11=24。比较上述三种情况的增量，插入到（3, 0 ）间和（1,3）间增量最小，考虑到下一节点插 入时路程最小问题，所以应当将4插入到送货点3和总部0之间。接下来，用同样的方法， 将5插到4和0之间，能使该条路线总路程最小，该路线总路程为32km ,历时1. 9467h。 结果子回路为T=0-l-3-4-5-0）.因为街道平行于坐标轴方向，所以它就是最优化路线。第二条行程这中，由于所剩下节点中，2距离0点最近，因此由2出发，就可以找到最近 点 13 ,接着是7,然后6.这样，第二条优化路线0-2-13-7-6-0就确定了。用这种方法，依次 可确定以下剩余六条路线。得到总的送

25、货路线为：（1 ） 01 3 4 5 0（2） 02 13 7 6 04016172014 15 235)019113222 06)018242507)027260802930280运输员序号所经站数最近点所用时间(小时)总载重(kg)总路程(km )141 (3, 2)1. 94672432242 (1, 5)2. 346724.242349 (10, 2)1. 866422.9304616 (2 ,16 )4. 600023.5905411 (17 , 3)4. 213424.9726318 ( 11 ,17)3. 750024. 7687227 ( 21 ,13)3. 706722768

26、329 ( 25 ,16)4. 840018. 396合计3028. 2699184. 5506改进前和改进后的路程，时间比较如下:路程L匕较然后，根据所经历的时间进行划分，确定运送人数。在工作时间小于6小时的前提下，最 终只 需要六名运输员，第一条线路和第二条线路有一人完成，第三条和第七条线路由一人完 成，则各运输员到达各站点时间的情况如下：路线站点编 号到各站点时 问出发时间路线站点 编号到各站 点时间出发时间119： 129： 0051910 ： 059： 0039： 321110 ： 4149： 523211 ： 08510 ： 112211 ： 322212 ： 0211 ： 586

27、1810 ： 079： 001312 ： 482410 ： 31713 ： 102510 ： 53613 ： 3972713 ： 4512 ： 233109： 349： 002614 ： 07129： 5882910 ： 389： 00810 ： 203011 ： 00910 ： 442811 ： 244169： 439： 001710 ： 072010 ： 291410 ： 511511 ： 302311 ： 59路径为:200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 23 29 3方法二

28、：每一个行程的第一个送货点是距离总部最远的未服务的送货点。分析方法如一：得到的路径为：(1) 030 29 28 23 15 0(2) 026 27 8 0(3) 024 25 14 9 04) 0181720165) 0322211106) 019 13 7 07) 012438) 05 2 1 0同方法一，用最近插入法修改路径可以得到更优的解,改进后的路径为:1) 028 30 29 23 15 02) 0262780141716 6 022103) 24255)11326)194) 20187)128)02 5 1 0运输员序号所经站数最远点所用时间(小 时)总载重(km )总路程(km

29、 )1530(28 , 18 )4. 833324. 11002326(20 , 17 )3. 540024. 3763424(15 , 19 )3. 386722.4684518(11 , 17 )3. 153024.4585432 (22 , 5 )2. 826723.6546319(15, 12 )2. 660020.8547312(14, 6 )2. 180024.242835 (3, 11)1. 620020. 728合计3024. 1997184. 5480改进前后路程和时间的比较如下:然后，根据所经历的时间进行划分，确定运送人数。在工作时间小于6小时的前提下，最 终只 需要五名运

30、输员，第三条线路和第八条线路由一人完成 第四条线路和第七条线路由一人完成， 第五条线路和第六条线路由一人完成，则各运输员到达各站点时间的情况如下：路线站点编号到各站点时间出发时间路线站点编号到各站点时间出发时间12810 ： 469： 005119： 489：003011 ： 113210 ： 152911 ： 332210： 392312 ： 051011： 061512 ： 3461913 ： 5512 ：5022610 ： 299： 001314： 312710 ： 51714： 53811 ： 477413 ： 3613 ：1032410 ： 229： 001214： 122510 ：

31、 44314： 481411 ： 118213 ： 4813： 34911 ： 45514： 074209： 509： 00114： 391810 ： 171710 ： 411611 ： 07611 ： -11路径图为:法一的距离短，时间短，所以若是只考虑时间和路程，改进后的方法二为最优解。7.2问题二模型问题二中由于业务员所得的费用是最主要的，业务员安排、路线选择都是为了总费用的最小化 提供条件，所以应首先考虑路费，之后再考虑业务员的安排。为了使总能够费用最少，总的思 路是先送货给离快递公司最近切块间最重的送货点，以此类推，在保证时间、载重量有限的 前提下，沿途把快递送完，最终让业务员最远点

32、空载返回。根据这一思路，全部路线业 务员的 重载费用可表示为：30M 重 3Ti（ xi yi） il从上式可以看出，业务员的重载费用是恒定的，又由于总费用为重载与空载费用之和，所以 总费用的确定就可以转化为满足一定条件下的各路线的最远点的选择问题。某路线业务员经过 的路径选择应遵循以下原则：一是，近者优先原则。某业务员最近起始送货点的选择直接 关 系到费用的多少，所以该业务员在沿途往送货终点站中应尽量把较近点的快件送完，不让下 一条路线再把较近点作为起始送货站。二是，不走冤枉路原则。一方面，离原点（快递公司）较 远的送货点坐标应分别大于离原点较近送货点的坐标，在各个坐标上均不走回头路，即按图

33、（a ） 中的路线前进，而不按路线前进：图（a）业务员行走路线约定另一方面，由于在路途相等的条件下，重载费用要比空载费用大得多，因此，尽量让业务员空 载行走。三是，坐标贴近原则。在同一条路线中，离原点较近送货点的坐标仅次于较远点的坐 标。四是，路线较少原则。路线多，一方面，相对最远点的选择多，跑的空路多，费用就多；另 一方面，过分地强调短暂效益，出动路线多，会引起业务员的反感，不利于以后的人员控制。 根据上述分析及基本假设，业务员送货的费用可以表示如下：30重载费用：''重3TiilN 30空载费用：M空k 1 i 1总费用：应"总该乂重乂空 满足(XIyi2bi (

34、xi .yi时间约束:x yi xi yi ji 2030mj30ai)载重量约束：Ti * ai 25路线约束：ai xi ai 11 1'iai lyi 1根据路线约束条件以及表二知：送货点1 (3, 2 )、2 (1 , 5 )首先必须作为某路线的 最近起始送货点，再结合时间约束条件、载重量约束条件以及上述分析的有关内容，依次 选出各路线的次近点，并做统筹兼顾，一直到满足约束条件的最大值为止。随后又选出6 (0, 8)、9 (10, 2)、10 (14, 0)、16 (2, 16)、22 (21 , 0 )、15 ( 19 , 9 )、25(15 , 14 )为某条路线的最近点，

35、分别确定次近点等，最后确定各路线如图(b )所示：第一条路第三条路线：出 w IIIF 田I瓶回 rr返回线出发线第八条路线:返回线出发线第九条路线:返回线图（b）业务员行走路线根据上面确定的路线，把个业务员所经过的送货点数、最近点、所用时间、总载重量进行归 纳，并用C+编程求出各业务员送货所得费用以及总费用，如下表：路线号所经送货点数最近送货点所用时间（小时）总载重量 （kg）费用（元）141 (3, 2)2.4166722. 1792.9242 (1, 5)2.524. 7969. 5356 (0, 8)4. 6666723.81852.4439 (10, 2)2.7521.91498.

36、25410 (14 ,3. 6666719.21352.46416 (2 ,4. 3333322.92261.87222 (21 ,3. 7514.91506. 78215 (19 ,3. 1666715. 11577. 69225 (15 ,3. 4266719.62019.2合计30184.513830.7根据时间约束，最少要8个业务员送快件，其中把路线1和2合并，让业务员A执行任务， 其余的分别由其他7个业务员送货。同时，为了便于统筹业务员，可以得出各业务员到各送货点 的时间（各业务员的出发时间为0 ）以及各路线从快递公司出发的参考时间（从9 ： 00开始工 作）。第一个人：0-1-3-

37、8-13-0 和 0-2-4-7-14-0第二个人：0-6-5-20-18-30-0第三个人：0-9-12-19-0第四个人：0-10-11-32-23-0第五个人：0T6-17-24-28-0第六个人：0-22-29-0第七个人：0T5-27-0第八个人：0-25-26-00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30若根据问题一的求解方法，可得以下8条路线:第一条路线：第五条路 线：第六条路 线：第七条路线:图（b）业务员行走路线根据上面确定的路线，把个业务员所经过的送货点

38、数、最近点、所用时间、总载重量进行归 纳，并用C+编程求出各业务员送货所得费用以及总费用，如下表：路线号所经送货点数最近送货点所用时间（小时）总载重量 （kg）费用（元）141 (3, 2)2.0333324767. 5242 (1, 5)2.7333324.21390. 63410 (14 ,2. 5666722.91357. 54416 (2 ,3. 117. 71438. 45522 (21 ,5.222.92680. 66319 (15 ,3. 33333252310.27318 (11 ,4.1666723.526208327 (21 ,4. 3333324.32891.9合计302

39、7. 46666184. 515456.7合并则有以下人员分配：第一个人：0-1-3-4-5-0 和 0-19-25-24-0 第二个人：0-2-13-7-6-0 和 0-10-12-8-9-0 第三个 人：0 -16-17 - 20-14 - 0第四个人：0-22-32-23-15-11-0第五个人：0-18-26-28-0第六个人；0-27-29-30-0 八模型评价1、模型的优点：（1）模型系统的给出了业务员的调配方案，便于指导工作实践。（2 ）模型简单明了，容易理解与灵活应用。（3 ）模型的方法和思想对其他类型也适合，易于推广到其他领域。（4 ）本模型方便、直观，易于在计算机上实现和推

40、广。2、模型的缺点：（1 ）模型给出的约束条件可能也有不太现实的。（2 ）对街道的方向，客户的快件量的假设有待进一步改进。3 、模型的推广（1）本模型不但适合于快递公司送货问题，还是用于一般的送货以及运输问题，只需要稍微 改动模型即可。（2 ）模型方便、直观，可以实现计算机模拟。（3 ）建模的方法和思想可以推广到其他类型，如车辆调度问题等。参考文献：1：姜启源、谢金星、叶俊编，数学模型-3版，北京，高等教育出版社，2003. 82：吴建国、汪名杰、李虎军、刘仁云编，数学建模案例精编-1版，北京，中国水利水电出版 社，2005.53：唐焕文、贺明峰编，数学模型引论-3版，北京，高等教育出版社，2

41、005. 3注释：C+源码 求解路线及其相关内容：问题一之方法一：#include<iostream>#include<fstream> #include<cmath> #define max 1000 using namespace std; struct ver int x; int y; int num; float weight;；bool visited31;ver v31;int nextl () int k,min=max, tag=0;float w;for (int i=l;i<31;i+) if (visitedi=false&am

42、p;&vi. x+vi. y<min) min=vi. x+vi. y; k=i;w=vi. weight;tag=l;if (visitedi=false&&vi. x+vi. y=min&.&vi. weight>w) k=i ; w=vi. weight;tag=l;if (tag)return k;else return 0;int next2(int k,float w) int min=max, tag=0, m, i ; for(i=l;i<31;i+)if(visitedi=false&&fabs(vk.

43、 x-vi. x)+fabs(vk. y-vi. y)<min&&w+vi, weight< =25) min=fabs(vk. x-vi. x)+fabs(vk. y-vi.y); m=i;tag=l;if (visited i=false&&fabs (vk. x-vi. x) +fabs (vk. y-vi. y) =min&&w+vi. weight <=25&&vi. weight>vm. weight)m=i;tag=l;if(tag)return m; else return 0;)void

44、way () int k; float w; k=nextl (); while(k!=0) float time; int num_of_station=0, distance, tag; visitedk=true;w=vk. weight;distance=vk. x+vk. y;time=(vk. x+vk.y)/25.0;cout«，0" «z/->z/«vk. num«/->/;tag=next2(k, w);while(tag!=0) num_of_station+; visitedtag=true; cout<

45、<vtag.->； w=w+vtag. weight;time=time+(fabs(vk. x-vtag. x)+fabs(vk. y- vtagL y)/25. 0;if(time+(vtag. x+vtag. y)/25. 0+(num_of_station+l )/6.0<=6) distance=distance+fabs(vk. x- vtag, x)+fabs(vk.y-vtag.y); k=tag;tag=next2 (tag, w);elsetime=time-(fabs(vk. x-vtag. x)+fabs(vk.y- vtag. y)/25. 0; b

46、reak;time=time+(vk. x+vk. y)/35. 0+ (num_of_station +1)/6. 0;"z<<w<<endistance=distance+vk. x+vk. y;/z/z<<distance<</zkmk=nextl ()int main() int i;ifstream infile(1.txt)；cout«/z各站点的坐标及相关信息是：z，«endl;for(i=0;i<31;i+) visited"= false;infile>>vi. num>>vi. x>>vi. y>>vi. weigh