物流优化调度数模论文

1、1、 问题重述 物流调度是城市发展过程中亟待解决的现实问题。在如下图所示的城市中有N=31个物资仓库，任意两个仓库的运出物资互不相同，仓库的位置坐标见附表1。我们约定序号为i ( i取值0, , N-2 )的仓库与序号为i+1的仓库之间有道路直接相连，同时，任何两个仓库之间，只要他们之间的直线距离介于10到15之间，也都有道路直接相连。现在有一些物资需要在仓库之间周转，周转任务见附表2。假设每个仓库的卡车数目与每台卡车的载重没有上限，但是每一条道路的任一侧都有同时在运的重量上限Wmax=50。汽车以每小时10个单位长度的速度在道路上行驶，可以在途中的任何一个仓库休息以等待可用的道路。试问：（1

2、） 若全部完成运输任务1（不用返回），最少需要多少时间？（2） 假设同一仓库的运输任务1和任务2所运物资相同，那么同时完成各自的两个任务（都不用返回）最少需要多少时间？2、 问题背景近年来，物流作为“第三方利润的源泉”受到国内各行业的极大重视并得到了较大发展，大量规模较大的生产企业、商业企业纷纷建立起配送中心向商品流通的效率化发起挑战，与此同时，相当部分的大型运输、仓储和航运企业也开始朝向第三方物流经营。物流配送开始在我国迅速兴起发展起来。如何在提高物流配送效率的同时降低成本成为一个重要的研究课题。高效率合理的配送是物流系统顺利运行的保证，配送线路安排的合理与否对配送速度、成本、效益影响很大。

3、正确合理地安排车辆的配送线路，实现合理的线路运输，可以有效地节约运输时间，增加车辆利用率，从而降低运输成本。3、 基本假设（1） 每个仓库的卡车数目与每台卡车的载重没有上限。（2） 卡车可以在途中的任何一个仓库休息以等待可用的道路。（3）不考虑各路段流量限制，无道路拥挤、堵车等耽搁、延误事件发生。（4）假设各仓库派出的运输车辆无抛锚等意外事件发生，并且汽车始终以每小时10个 单位长度的速度在道路上行驶。（5）假设车辆完成运输任务不用返回。（6）两仓库间的距离四舍五入为整数。4、 符号说明符号含义D最短路长矩阵R最短路线矩阵A带权邻接矩阵5、 问题分析（1） 问题一附表1: 仓库序号i仓库横坐标

4、X_i仓库纵坐标Y_i040.865161032671724.4626319200009143.434735268175516.885970491068924.2217922755455245.0026923208831319.989132454944818.4623390560108412.99352014253275.56013776468937540.003424011215439.0126034160569621.570691373177219.4869418480627745.532379721476212.084564295691689.0923514151426320.19560

5、72794057913.19014582609954.82272625841943107.276949019235856.59866463031675116.8034279354331947.10252953877431243.464610382004547.80672701149011328.985229368278528.76042975392331427.49301009181662.98897714735779157.2477399111863411.73899566862031642.651555886094717.65792856110361731.102756574253341.

6、05970200989801817.54761904461350.7701718825777531925.66247699335272.151190082890392020.09040168759718.44950147313522213.7983345845421032.45577374782262211.995807677682936.5861192829335236.1659467417582832.3872981568153249.1953894141208422.54618532154722511.997626283245127.35044461431732620.863353454

7、218514.8160402803887272.4827215162871137.23464035370782845.13580549576409.447750751627232947.239359486082334.33877166826583024.54320462340409.17555778686349 本小问主要解决的是若全部完成运输任务1（不用返回），最少需要多少时间的问题。 首先本小问属于图论问题1。由附表一的相关数据信息，我们先把31个仓库两两之间的距离用matlab程序2逐一算出（距离见附录一），根据题意，我们知道两相邻仓库之间有道路相连，再利用matlab程序2找出直线距离

8、介于10到15之间的仓库（matlab程序2见附录二），从而确定出仓库间道路连接情况。我们把题目中的仓库坐标图当作了赋权图，写出了带权邻接矩阵。之后用Floyd算法1转化为matlab程序2（该程序见附录三），最后得到了关于路长的矩阵D和关于路径的矩阵R。根据运输任务一中每一组任务的出发仓库和目标仓库，利用矩阵R追溯出仓库之间的最短路线，再利用矩阵D找出对应仓库间的最短路径长度。我们分析了得到的31条最短路线，发现各条路线之间基本上不相冲突，所以各仓库可以同时派出车辆运输。又考虑到每一条道路的任一侧都有同时在运的重量上限Wmax=50，所以我们把运输量超过50的货物分为两次运输。于是把两次运输

9、所需的最长时间相加，就得到了题目要求的最短时间。（2）问题二 本小问主要解决的是若同一仓库的运输任务1和任务2所运物资相同，那么同时完成各自的两个任务（都不用返回）最少需要多少时间的问题。针对第二个问题，我们仍旧采用Floyd算法1，根据运输任务二中每一组任务的出发仓库和目标仓库，利用矩阵R追溯出仓库之间的最短路线，再利用矩阵D找出对应仓库间的最短路径长度。我们分析了得到的31条最短路线，发现任务一和任务二的各条路线之间基本上不相冲突，所以各仓库可以同时派出车辆运输。同问题一，我们把运输量超过50的货物分为两次运输。于是把两次运输所需的最长时间相加，就得到了题目要求的最短时间。6、 模型建立（

10、1） 问题一 根据题意，我们知道两相邻仓库之间有道路相连，再利用matlab程序2（见附录二）找出直线距离介于10到15之间的仓库（仓库间的道路连接状况如下表）：仓库号与该仓库有道路相连的仓库号01、5、7、13、2912、021、3、21、22、2332、4、8、13、15、20、24、25、3043、5、14、19、26、3054、6、065、7、8、13、20、24、25、3076、8、087、9、10、21、23、26、398、10、14、19、26、30108、9、11、18、201110、12、21、22、23、271211、13、17、29130、3、6、12、14、17144、

11、13、15、18、261514、16、20、24、26、31615、171712、13、16、181817、19、10、14194、9、18、20、26206、10、3、19、21212、8、11、20、22、24222、11、21、23、24232、8、11、22、24243、6、15、23、25、26253、6、24、26264、8、9、14、15、18、19、24、25、272711、26、282827、29290、12、28、30303、4、6、9、18、2931附表2: 运输任务1运输任务2出发仓库目标仓库运输量目标仓库运输量0736.8484596490337241.3168303

12、6582781962.5618560729690947.714180053371321178.02274351513771666.00747564510403138.112576886578532355.776544053070641592.93859709687303096.092644989262551777.5712678608402665.590196777383161948.67916324031721342.990268680730172143.58585885809192095.125231599186882344.67837494298062798.98223973805029

13、2530.6349472016557366.2472620661491102750.85086553811271033.3345501605465112951.07715641721101750.800068495236012081.76277083222622463.931200998616613279.4831416883453077.129506287063414464.4318130193692751.206615566823515637.86093826602681477.642970665867916881.15804582824772184.3336101701856171053

14、.28255887994552847.0899919321760181235.0727103576883434.2662590394408191493.90015619998871154.4679606023878201687.59428114929841856.4604553582312211855.01563428984222565.1280860853294222062.2475086001228171.2641764606256232258.7044704531417829.2430841550689242420.77422927330281551.233020084544425263

15、0.12463302794912289.4994202645882262847.09233485175912917.0939397337613273023.0488160211559596.377079198222528184.43087926953891285.459397543830929319.47642895670491969.900570369888930522.59217809723992676.0608349299059根据附表二中的运输任务一，我们首先利用matlab2和画图软件画出了0号仓库到7号仓库的赋权图1。 后来，经过再次审题，我们认为如果要求出0号到7号仓库间的最短距

16、离及最短路线，不能只考虑0号到7号仓库间的道路情况，因为最短路线可能涉及到0号到7号以外的仓库。所以必须把31个仓库间可通道路全部考虑进去。如仓库坐标图所示： 我们计算出了31个仓库两两之间的距离（见附录一），把上图转化为带权邻接矩阵1A（A是一个31行31列的矩阵）：A=0,8,inf,inf,inf,15,inf,13,inf,inf,inf,inf,inf,13,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,12,inf;. 8,0,48,inf,inf,inf,inf,inf,inf,inf,inf,inf,in

17、f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;. inf,48,0,31,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,13,11,13,inf,inf,inf,inf,inf,inf,inf,inf;. inf,inf,31,0,15,inf,inf,inf,11,inf,inf,inf,inf,14,inf,14,inf,inf,inf,inf,10,inf,inf,inf,12,12,inf,inf,inf

18、,inf,10;. inf,inf,inf,15,0,43,inf,inf,inf,inf,inf,inf,inf,inf,15,inf,inf,inf,inf,13,inf,inf,inf,inf,inf,inf,12,inf,inf,inf,12;. 15,inf,inf,inf,43,0,27,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;. inf,inf,inf,inf,inf,27,0,25,12,inf,inf,inf,inf,12,i

19、nf,inf,inf,inf,inf,inf,11,inf,inf,inf,13,12,inf,inf,inf,inf,11;. inf,inf,inf,inf,inf,inf,25,0,37,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;. inf,inf,inf,11,inf,inf,12,37,0,16,14,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,13,inf,13,inf,inf,13,inf,inf,inf,inf

20、;. inf,inf,inf,inf,inf,inf,inf,inf,16,0,6,inf,inf,inf,14,inf,inf,inf,inf,13,inf,inf,inf,inf,inf,inf,13,inf,inf,inf,12;. inf,inf,inf,inf,inf,inf,inf,inf,inf,6,0,41,inf,inf,inf,inf,inf,inf,12,inf,13,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;. inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,41,0,37,inf,inf,inf,i

21、nf,inf,inf,inf,inf,15,12,15,inf,inf,inf,11,inf,inf,inf;. inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,37,0,24,inf,inf,inf,14,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,14,inf;. inf,inf,inf,inf,inf,inf,12,inf,inf,inf,inf,inf,24,0,26,inf,inf,12,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;. inf

22、,inf,inf,15,inf,inf,inf,inf,14,inf,inf,inf,inf,26,0,22,inf,inf,10,inf,inf,inf,inf,inf,inf,inf,14,inf,inf,inf,inf;. inf,inf,inf,14,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,22,0,36,inf,inf,inf,13,inf,inf,inf,11,inf,14,inf,inf,inf,inf;. inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,36,0,26

23、,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;. inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,26,0,43,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;. inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,12,inf,inf,inf,inf,inf,inf,43,0,8,inf,inf,inf,inf,inf,inf,14,inf,inf,inf,11;. inf,i

24、nf,inf,inf,13,inf,inf,inf,inf,13,inf,inf,inf,inf,inf,inf,inf,inf,8,0,8,inf,inf,inf,inf,inf,14,inf,inf,inf,inf;. inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,8,0,29,inf,inf,inf,inf,inf,inf,inf,inf,inf;. inf,inf,13,inf,inf,inf,inf,inf,13,inf,inf,15,inf,inf,inf,inf,inf,in

25、f,inf,inf,29,0,9,inf,11,inf,inf,inf,inf,inf,inf;. inf,inf,13,inf,inf,inf,inf,inf,inf,inf,inf,12,inf,inf,inf,inf,inf,inf,inf,inf,inf,9,0,7,14,inf,inf,inf,inf,inf,inf;. inf,inf,13,inf,inf,inf,inf,inf,13,inf,inf,15,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,7,0,10,inf,inf,inf,inf,inf,inf;. inf,inf,inf,12,

26、inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,10,0,6,14,inf,inf,inf,inf;. inf,inf,inf,12,inf,inf,12,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,6,0,15,14,inf,inf,inf;. inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in

27、f,inf,inf,inf,inf,inf,15,0,29,inf,inf,inf;. inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,11,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,29,0,51,inf,inf;. inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,51,0,25,inf;. 12,inf,inf,in

28、f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,25,0,34;.inf,inf,inf,10,12,inf,11,inf,inf,12,inf,inf,inf,inf,inf,inf,inf,inf,11,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,34,0之后，我们把Floyd算法1转化为matlab程序2（见附录二），利用写出的邻接矩阵1得到了最短路长矩阵D和最短路径矩阵R。56D中数据如下所示（D为31行

29、31列的矩阵，例如表中的表示56）：085646481525133748516237133960512547443650554838375051371236804854562333214556597045214768593355524458615646455859452044564803134633661243438256245484581572921131113202228353687684056643101548214611222537381430145026211810242922121224266944105866461504323482624305253291529654121132

30、139443727271241714612152363484302728395053645228546266404946385257504039525352273842503621232702512232637361237355024221911253023131225267045116775614648522503748516261376260754947443650554838375051957036546226112639123701614284824302561362629211320132323133780552158664222245023481606445935143672471

31、813192936293428134271461264724828305629542260416541204278531219133542354034194877521863712537526740652844410375158517751534638151215253139116251472634625759413639485962370245071401457554752495249486148391447505848333539123724353849240264738123431233742352524373863382367754015305326511428224250260225

32、838101825273427272714418055217078341429562954253439365228220364029211337282111171431825824106114705065926590617075728864583602665574973645747535067118946010010895646492659075615596101777562260435159889083737257861138854576552212149224732181253583432356943081645504333291443704511657350281356305529131

33、952664227427751808374642352914437853197381423621643863372127447450355085591680293845403722518661276761132338522550132927155237433773493934260916111725267766336961132641593257203634124940504076524234269071420282374633667611322375225501329271552364336724839342616701016242677663260682312274518432334372

34、550264226623833302226171006142071562254622912273912372334372548244226623633302232231660151465562269774427425427523849524063395741775148453747383121150298071377482364863785176395552114862696288626457492623263642290516258374587697152625074717762745076838862707873777477757480510255912206844462737254946

35、527449255158633745534862676050495863250344654411012381136211218474723262460351119203439322222243659340R中数据如下所示（R为31行31列的矩阵）：（注：R中131对应题中仓库号030）1223131614814311428141414311814312114142525141414263030141233131114114311428141143118143121141432514141426301142234212222222221222323421416142121212223232225

36、212328221313134531313193192514145161614312121925252526926313131664456313143131251441541614202020925254427263131311125315671731928141143118143121792525779263017662531316789319281414313118143121219252525269263131317725313177893192814731311814312179252577926313177722447789101122147104161411104222424442

37、726313143131223131313131910112231311515163111201192492727272731313131312231313131311010111231311015163119102110241027271027313110303023252522222222221112132522251813112323222324242525282813253030233131301430143114121314143118181821141212121414141230301430302531317777319281314153118183121792525779263

38、013731312244999919192214141516161419194924944272631311931312544262626421925144151617142121212525252525272628314313125161626262616211625161616161718212116252525162516262831163131313120313131311919193131191717181919202125251727192731311931313131203131313111111131311131181819202021313131272727313131313

39、122555313110101022145105191919202121221027272727313119313122202020313120202022202020202020202021222223222720273131209332525999999121291025251411213222323252525122813253332525242424242424121225242525252121322232425252512281325933252599999912122510252525112132323242525251228132526262444262626431924144

40、541614312142424242526272628314772544777431928147541614312142525252526272828314262626262626262626312628262626262626312626262626262627282831263030232525222222222212121225222518131223231212122425272829132530302831313030303031312830303031303031313028282830302828293030112313111411431312814114311814313114

41、14252514143126293031303044577741010251471041614191949252544526303031之后我们利用矩阵R追溯出任务一中从出发仓库到目标仓库之间的最短路线，利用矩阵D找出最短路径长度如下：出发仓库目标仓库路线路径长度070713191013630956211222112531331314415431529517501317406196201919721782150823823139259262528102710926274811291112295112012290261321362423248144143430156152425629168161

42、538611710171810551812183061312581914199142720162019181716852118218101839222022212202623222322724242424025262526152628262728802730272433058281282901452932930344305306538我们分析了得到的31条最短路线，发现各条路线之间基本上不相冲突，所以各仓库可以同时派出车辆运输。又考虑到每一条道路的任一侧都有同时在运的重量上限Wmax=50，所以我们把运输量超过50的货物分为两次运输。于是把两次运输所需的最长时间相加，就得到了题目要求的最短时间。（2） 问题二我们利用矩阵R追溯出任务二中从出发仓库到目标仓库之间的最短路线，利用矩阵D找出最短路径长度如下：出发仓库目标仓库路线路径长度0201256191013630956216231516813233242322430430125656276136131272076203682783252737939303221010101001117111217511224121362449130131229050147148751151415142216211615242322217317281718302928113184181942119111920211152201820