快递员的送货策略问题

1、快递员的送货策略问题摘要 在货物运输的过程中，合理的选择货物路线很重要，他不仅可以加快配送速度，提高服务质量，还可以降低配送成本，增加经济效益本文构建货物路线的规划模型，运用图论思想，Dijkstra算法，经典Floyd算法，利用lingo与MATLAB进行编程求解，给出了最佳的送货路线，另外将货物的分配问题转化成旅行商推销问题，进行编程求解；根据运输路线策略中的成组法，用射线旋转法进行区域划分，以送货员最大承受力为50公斤，货物体积不大于1立方米为依据，利用整体规划进行区域规划，从而得到最优化模型问题一以最快完成送货任务并返回仓库的路线与方式，分析题知尽可能地缩短路径可以达到尽快完成任务的目

2、标在题目所给的各个点的坐标基础上，为确定最短路径，先应用Dijkstra算法求解出任意两点的直线距离，运用Floyd算法，借用MATLAB求出任意两点之间的最短距离，应用lingo软件进行优化求解，求得遍历路程结果为125499.5m，时间为493.7min问题二在问题一的前提下进行了对送货时重量和体积的约束，经过分析，快递员需要在送货途中返回一次仓库，进行补货根据问题一中最小生成树，根据聚集原则，将区域分成两部分，进行分次求解，第一部分路程为67554.8m,时间为261.9min ，第二部分路程为66624.56m，时间为246.8min 关键字：Dijkstra算法；经典Floyd算法；

3、0-1规划法；最小距离一、问题重述小张是某快递公司送货员，其负责送货的区域如图，该区域包含50个送货地点，仓库在图中O点处送货时，小张只能沿图中的道路行进，没有其他道路可选送货时，小张的平均行进速度为24公里/小时，每件货物交接时间3分钟（如同一地点有多件货物，交接时间也按每件3分钟计算）根据某天小张的送货清单，请你们帮助他解决下列问题：1. 设计最快完成送货任务并返回仓库的路线与方式，给出结果并注明送货路线2. 实际上小张每次送货时，只能装载重量不超过50公斤，体积不超过1立方米的货物这样，小张不能将全天的货物一次取走，只能中途返回仓库取货在这种情况下，设计最快完成送货任务并返回仓库的路线与

4、方式，给出结果并注明送货路线以上两种情况都不考虑中午休息时间 图1 送货地点示意图表1：送货地点坐标编号X坐标（米）Y坐标（米）07750500011245581502154308730314565592041120151155155006815679257175776451522087440323098955635108615183511840442512134758840146135134201563655140166475115651717655085184935872019563511652069451235219401297022590066052367579902415005133

5、80251332021552671651380027604514435281372059752955005615331667082103210800837033370076553417851820351295040653615330122653743902085387835101453923501107040118159415415100147504218552735431067525954444909590453950649046458536104714508265484625695491500136705二、 问题分析 在日常生活中购物送货问题，如何在有效的时间内送到货物且能最大限度的节约

6、成本，合理规划过程中的最短路线我们需要在考虑题的过程中重点分析各个点的路径问题，送货员能承受的重量体积等因素条件下，规划处最优路线首先我们利用excel处理数据，求出总重量，总体积等数据，在求出每条路的总距离，对于送货员能承受的重量等情况，我们利用射线旋转法进行划分，0-1型规划法对问题进行巧妙的转化，从而求解 对于问题一：不考虑装载重量和物体体积，最佳运送方案就为找出一条走遍所有送货点然后返回出发点的最短路线根据表1和表2所给出的送货点位置信息即可计算出所有直通点的距离根据以上数据即可利用Floyd算法算出任意两点间的距离矩阵然后运用lingo软件就可以得到最优路线 对于问题二：由于质量和体

7、积的约束，综合总的质量与体积得出送货员将货物的分配问题转化成旅行商推销问题，进行编程求解，根据运输路线策略中的成组法，用射线旋转法进行区域划分，以送货员最大承受力为50公斤，货物体积不大于1立方米为依据，利用整体规划进行区域规划，从而得到最优化模型三、问题假设1. 假设送货员只能沿如图路线图行驶，不能走其他的任何路线2. 在联通线路中，送货员可自由选择路口3. 交接货物只需要3分钟，行进速度总是24公里/小时，路上行进畅通无意外阻碍4. 如果要从任意一点出发前往另一点，送货员必然选择最短路径5. 送货员路程中都是匀速行走6. 不考虑送货员中午休息及中途休息四、符号说明表示送货点i到送货点j之间

8、的距离表示最短距离和表示矩阵中任意的位置，0-1决策变量 ,表示送货的路线表示经过路程所花费的总时间表示路程表示从 个点到 点运送货物的质量表示从 个点到 点运送货物的体积五、模型建立与求解5.1模型分析 不考虑装载重量和物体体积，所以最佳运送方案就为找出一条走遍所有送货点然后返回出发点的最短路线根据表1和表2所给出的送货点位置信息即可计算出所有直通点的距离（程序见附录3）根据以上所得数据，即可采用0-1规划模型寻找送货点间的最短路径 图2坐标点之间的关系5.2模型的建立 利用图论思想，将已连接的送货点一一标明，送货点抽象为下列图的顶点任意两顶点间都有通路讲两点之间的路线权值赋为，两坐标间的距

9、离这样送货点的分布图就构成了加权网络图见图（2）问题就转化为在给定加权网络图中寻找从原点0出发满足做给约束条件下，行遍所有顶点，并再回到0点，使得总权最小 设假最佳送货路线问题由送货点1，2，3,n组成，W表示送货点i到送货点j之间的 距离决策变量定义为： 1，选择从送货点i到送货点j, X= 0, 否则，其线性（整数）规划模型为： 引入0-1决策变量xij=0，最短路经过弧（i,j），xij=1，最短路不经过弧（i,j）考虑最短路径唯一和，必须从O点出发并反回O作为约束条件目标函数是路径上所有弧长度之和最小，我们建立0-1规划模型： 1.上式目标函数（1）给出了送货路线的总长度2.约束（2）

10、保证由送货点i到送货点j，3.约束（3）保证i只能到一个送货点 4.（4）式保证了经过全部送货点在以上约束下用MATLAB和lingo软件求解最佳路线5.3模型的求解（1）求任意两点之间的直线距离： 根据Dijkstra算法，并运用MATLAB，可求出任意两点间的直线距离（程序见附录3，结果见附录4） 从中选出可行解：序号地点1地点2距离1062182.022081796.9430151392.0641401417.6852121958.0962363536.417351294.3184212152.549521916.28105122863.78116222103.69127261948.9

11、3138101823.91148152191.74158464775.74169202197.641710201774.511811233568.811911421971.382012401756.772113411325.682214261097.862316141885.92416381966.222516394154.592617233102.762717422351.722818331630.782919201311.8730194811143120101774.51322142152.543321234987.053422151537.033522182324.75362333304

12、3.493724301252.943824505004.543925351945.514025432681.354126271287.494227131017.894327394997.62442851968.25452865917.944629221067.76473077823.324830362292.64493122178056513263113.465232383455.75333173217.015433181630.785534372618.44563565909.555735282059.375836302292.645937461537.426038

13、312258.646139212366.036239442601.926339492735.426440165756.576540321456.796640504805.786741131325.696841493758.516942111971.38704234917.6771436534273734392607.687443102195.727544332090.057645291779.927746173182.467846292203.927947332331.228048371409.73814941494.138250164235.48350262860.

14、98（2）求任意两点间的最短距离： 运用经典Floyd算法，并借助MATLAB，可解出任意两点间的最短距离（程序见附录5，结果见附录6）（3）求快递员遍历的最短距离： lingo是一种用来解规划的常用软件，故本问采用lingo进行求解（程序见附录7）由lingo计算出的结果可以给出送货路线如下：015810209194837461734421123334744182229453138161472641131750243036253123214021449394325352860总路程为125499.5m,时间为493.7min5.4问题二模型的建立与求解1 模型建立： ; ; ; ； ； ；

15、；2 模型的求解：送货员将60个包裹最快送到50个指定地点，经过计算60个包裹的总质量为87.73公斤，总体积为1.7588立方米，送货员每次携带货物质量不能超过50公斤，体积不能超过1立方米，可以将路线分成两个片区根据最小生成树，和聚集原则还有根据分组，我们在每一个最短区域根据分动态线性规划寻找最短最佳路线，根据运筹学中满载率的规定为80%-90%，为使用时时间最短，两个子区域区域区分如下：区域10，4，8，9，10，11，15，17，18，19，20，21，22，23，29，31，33，34，37，39，42，43，44，45，46，47，48，49区域20，1，2，3，5，6，7，12，

16、13，14，16，24，25，26，27，28，30，32，35，36，38，40，41，50根据遍历程序，解得区域一的最短遍历路径，即路径1为：01581043920194837461742344211232144939443347331822294529223122150；第一区域路程为67554.8m，用时261.9min解得区域二的最短路径，即路径2为：0635253528535236302450267262713411327261416383240124013260 第二区域路程为66624.56m，时间为243.8 min 六、模型的优缺及评价6.1模型的评价在现实的物流配送中，人

17、们多数是按照经验去制定送货路线而此模型在运用满载率原理对送货区域进行合理化而科学划分的基础上，用0-1整数规划的方法对路线进行优化，得到最优的送货路线和最优的分配方案，非常贴近生活实际对现实的物流派送有较强的指导意义以此，物流公司或其他机构可以根据这个采用划分区域，进行线性规划的方法提高自己的送货情况的路径优化，可以提高自己的效率，降低成本，提高企业竞争率有利于降低社会交易话的成本6.2模型优点1、模型是从简单到复杂一步一步的进行的，使得更加贴近实际2、本文模型简单，算法直观，容易编程3、本文注重数据的处理和储存方式，大大提高了规划效率6.3模型缺点在建模和编程过程中，使用数据只是现实数据的一

18、种近似值因而得出的可能与现实有一定差距，不过差强人意，理论要求强计算比较复杂，这个模型在现实中运用可能还有一些其他因素影响，所以实际运用中需进一步考虑七、参考文献1杨丹,赵海滨. MATLAB从入门到精通M.北京:中国铁道出版社,2013.2. 谢金星,薛毅编.优化建模与lingoM.北京:清华大学出版社,20053. 薛毅.数学建模M.北京:北京工业大学出版,20044. 张杰.运筹学模型与实验M.北京:中国电力出版社,20075. 赵静.数学建模与数学实验M.北京:高等教育出版社,20036. 龚劬.图论与网络最优化算法M.重庆: 重庆大学出版,2009附录附录1：表2：道路连通信息序号地

19、点1地点21062083015414052126236735842195210512116221272613810148151584616920171020181123191142201240211341221426231614241638251639261723271742281833291920301948312010322143321233422153522183623333724303824503925354025434126274227134327394428545286462922473074830364931225032151326523238533317543318553437

20、5635657352858363059374660383161392162394463394964401665403266405067411368414969421170423471436724387343974431075443376452977461778462979473380483781494825016835026附录2表3：送货清单序号送货地点重量（公斤）体积（立方米）113.090.0145221.900.0332320.460.0133421.960.0406531.340.0043640.900.0339751.420.0462861.670.0559971.280.0557

21、1081.730.03481191.340.043112101.730.011413110.580.029914110.990.024015121.450.020616132.790.030317141.220.034418151.230.039919161.420.005120171.820.034821181.200.059022191.190.025023200.900.030024211.590.005525221.650.025226231.450.008027240.940.031228251.620.049229262.130.037930271.110.026631271.03

22、0.049732281.550.020933291.770.029034291.990.002935301.710.004236311.120.019137321.180.028638331.400.045739341.520.011840352.330.015641351.300.042042360.480.048643361.370.027144371.140.002445381.360.018346390.870.004147401.700.049148411.710.014449421.170.016050430.060.050751442.370.030352451.180.0133

23、53460.900.034554461.310.024855472.050.059156482.510.025757491.110.042958491.550.058659501.770.056660502.120.0093附录3： x=7750,12455,15430,14565,1120,15500,7925,7645,7440,8955,8615,840,13475,6235,6135,6365,6475,1765,4935,5635,6945,940,5900,675,15005,13320,7165,6045,13720,5500,15440,6670,10800,3700,1785

24、,12950,15330,4390,7835,2350,11815,5100,1855,10675,4490,3950,4585,1450,4625,1500,10025;y=5000,8150,8730,5920,15115,6815,7175,15220,3230,635,1835,4425,8840,15435,13420,5140,11565,5085,8720,1165,1235,12970,6605,7990,13380,2155,13800,14435,5975,5615,14555,8210,8370,7655,1820,4065,12265,2085,10145,11070,

25、9415,14750,2735,2595,9590,6490,3610,8265,695,13670,13875;distance=zeros(length(x);for i=1:length(x)distance(i,:)=sqrt(x-x(i).2+(y-y(i).2);end附录405662.1138537.8746876.81812094.2210687.919161.9465662.11303031.0113070.01613303.8912267.136219.3678537.8743031.01102940.12315669.85147807462.2426876.8183070

26、.0162940.123016288.5315190.689159.34612094.2213303.8915669.8516288.5301494.138990.9197959.6943324.7931916.2791294.31416603.4515588.178934.1612182.0294633.7387664.4016757.56110457.139135.9547021.39610220.548551.08210135.411592.086525.8456337.472733.7571796.9427025.4279700.0057615.88613460.8912011.541

27、0954.374528.2728290.06810366.037707.35516463.8315016.2713283.173281.0757390.8619694.5997217.32115249.0513809.0712122.286933.88212197.715211.8713806.1810693.679268.52913178.276893.5641231.4631958.0923116.80913857.1912912.386103.58310544.49579.12411380.0312646.1151255053.2614098.58573.4848228.93110411

28、.211283.395293.6994641.7373916.521392.0586793.2479749.9918237.01411269.99819.8339470.7886687.6646886.4099393.0439864.7926424.8375402.0044235.3985985.60411120.7214142.7812827.2110050.728589.08912061.994665.0437541.5711049510028.87446.4926025.0917244.4554379.5499762.30612376.2410117.0614662.4613170.92

29、13446.793850.0978841.79411321.238945.03415052.7413574.8813009.8410483.1812483.0915097.6115340.92152.539896.43749129.9642449.1896734.6169764.0428692.0349760.5588323.1148358.7397680.86711781.0914773.5414043.47138.8835739.60111047.8811084.25818.5394669.3827472.96513992.9813508.115004.546254.5126057.083

30、6905.2683965.50817798.9216501.7512174.388819.4237739.9359696.1410809.926186.3765666.4912860.9839587.8188977.15610982.9512045.564971.7234608.9324019.2046049.0932516.1183242.549846.78815565.9814440.968721.4122332.5367402.58410407.129070.1310461.098993.4999418.23912265.167066.4175825.0098679.21914330.9

31、513968.065457.5293386.8135785.3118775.428220.4098858.987519.3426583.9394545.2611669.5584643.9754491.96211798.210704.25559.2854842.6778768.98211779.1611002.667893.5426404.7038870.9656759.70612406.3615294.9113421.5613311.6211853.4314602.085283.3914114.8825283.242459.5221618814945.1810236.7810499.36501

32、9.8463536.4146390.95114492.9813901.185543.9274448.23810091.0112885.5610873.7213434.0511940.0313067.415145.7025032.3387725.6887946.298354.1687249.6794325.398124.3410518.4313287.6613256.274227.8752735.4168171.5156001.3711417.6833679.3274447.19312119.1211158.154805.79910103.719882.10611956.1412944.3139

33、96.7023758.515002.1256315.1611903.0314839.8313102.9912401.810940.7613814.793786.7735833.2177761.9755117.39415749.5514381.811298.715629.8938094.12310973.7510722.626471.6715058.316999.8184081.6798665.48511696.510630.299077.4187586.4959562.6283456.789085.62111992.8510243.8512015.4610522.411617.397095.7

34、8911005.613987.73133236857.9445405.23110247.085319.64810811.3813465.1111229.6114839.8613346.0214243.3310687.9112267.0.681494.1308527.4649161.9466219.3677462.2429159.3468990.9198527.4640附录5：a=long; %调用附录3的建立的long表格n=size(a,1);d=a;for k=1:n for i=:n for j=1:n if d(i,k)+d(k,j)d(i,j) d(i,j)=d(i,k)+d(k,j

35、); end end endenddisp(d);附录6：012093.115595.217795.212647.911153.813169.412093.105132.67332.65936.27430.36223.515595.25132.603210.68233.49727.58520.717795.27332.63210.6010433.411927.510720.712647.95936.28233.410433.401494.19324.316500.96038.31916.31294.39139.110633.29426.4218211267.714769.816969.8121

36、73.610679.51234413416.710403.412700.614900.610382.68888.54179.91796.912892.716394.818594.8108519356.9139697492.915375.317672.519872.59439.1794513599.63620.814716.617260.519460.59027.1753313187.61172212339.514636.716836.710708.312202.415727.613637.13174.51958.14158.16275.37769.46562.614223.211209.913

37、507.115707.16578.35084.24986.410819.98977.411357.413557.49981.68487.53778.91392.11070114203.116403.113042.711548.611777.389347091.59471.511671.58384.168904235.47859.611873.514170.716370.710242.311736.415261.65253.811488.714990.817190.811813.813307.9125656707.216496.819998.922198.912113.510619.416274

38、5395.316491.11901.69307.514962.114246.33783.76080.98280.92152.53646.67171.82929.1916412666.114866.113469.712783.210240.39928.18770.711067.913267.97139.58633.612158.818173.9112287081.910292.514328.815075.15004.58497.815448.917746.119946.19512.78018.613673.211917.88904.511201.713401.78883.77389.626811

39、3205.31019212489.214689.27596.26102.13968.58099.917185.620687.722887.713517.612023.517678.13996.910231.813733.915933.914537.51385111308.119426.810961.658299039.614062.415556.56257.44709.27383.91689.611114.88460.210423.51669.65171.77371.75975.37469.46262.66884.611814.214111.416311.41018311677.114195.

40、88832.915142.917440.119640.113511.715005.817667.88091.517177.219691.621891.611458.29964.115618.719131.686693536.4674711769.813263.985506214.513973.117475.219675.214637.213143.115049.46967.85125.38627.410827.494318856.26201.68418.410165.712462.914662.94229.52735.4839011880.31417.73714.95914.94518.56012.64805.814912.311188.8252.63758.56312.19750.614225.216522.418722.41259414088.117613.35816.512767.615064.817264.86831.45337.310991.99215.814145.416442.618642.612514.214008.316527577612010.96316.615630.113087.24677.112435.715937.818137.813424.812237.1135129215.814145