送货路线优化问题

《送货路线优化问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、皖西学院本科数学建模课程设计2012皖西学院本科数学建模课程设计我们参赛选择的题号是（从A/B中选择一项填写）：14参赛队员信息(打印并签名)：姓名学院学号联系方式(Tel)。。。。。。。。。。。。。。。。。。日期：2012年6月10日皖西学院本科数学建模课程设计送货路线设计问题摘要当今社会，网购已成为一种常见的消费方式.随着物流行业的兴盛，如何用最短的时间，最节约成本的方案，完成送货任务显得尤为重要.针对本案例，我们采用了大量的科学分析方法，并进行了多次反复验证，得出如下结果：1：根据所给问题及有关数据，我们将题目中给出的城市

2、，及其之间的线路可看成一个赋权连通简单无向图，采用了求这个图最小生成树的办法，求出最优线路.在此基础上，我们通过观察分析计算对上述结果进行修正，得出最终结果.2：根据所给问题，我们发现当货物不能一次送完时，中途需返回取货，而返回路径当然越短越好，可通过求途中两点最短路径的方法求出.关键词：线路优化，赋权连通，最短路径.皖西学院本科数学建模课程设计目录一问题重述11.111.211.31二问题分析2三模型假设2四符号说明3五模型的建立与求解4六模型的优缺点分析7七模型的推广与改进7参考文献8附录9皖西学院本科数学建模课程设计一问题

3、重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位，现有实业公司，该实业公司生产专业生产某专用设备产品，专用设备产品该每件重达5吨（其长5米，宽4米，高6米），该实业公司库房设在北京，所有货物均由一货机送货，该机种飞机翼展88.40米（机身可用宽20米），机长84米（可用长50米），机高18.2米（可用14米），最多可装载250吨货物，起飞全重达600吨，平均速度为900公里/小时）将货物送至全国各个省辖市（图1所示红色圆点，除北京之外共

4、19个省辖市），假定货机只能沿这些连通线路飞行，而不能走其它任何路线；但由于受重量和体积限制，货机可中途返回取货.经过的各个省市都要一定的停靠费用和停靠时间（停靠时间为常量2小时），假设经过某个省市的停靠费用为：停靠费用=5000元×该省市的消费指数；1.1：若图示中19个省辖市每个省辖市只要一件产品请设计送货方案，使所用时间最少，标出送货线路.1.2：若图示中19个省辖市需求量见表1，请设计送货方案，使所用时间最少.1.3：若该实业公司为了花费最少，针对问题1和问题2分别求出花费、标出送货线路.省辖市新疆青海宁夏云南北京湖南海

5、南福建台湾吉林需求量（件）13540103498消费指数1.21.11.051.31.91.41.71.61.91.2省辖市甘肃西藏重庆内蒙古河南广西香港江苏上海黑龙江需求量（件）79125456973消费指数1.31.01.51.21.31.21.81.51.81.3表110皖西学院本科数学建模课程设计图1二问题分析当今社会，网购已成为一种常见的消费方式.随着物流行业的兴盛，如何用最短的时间，最节约成本的方案，完成送货任务显得尤为重要.针对本案例，城市可以看成点，而他们之间的连线既可以看成是时间，也可以看成成本，那么就构成了两

6、个赋权连通简单无向图，这个问题就转化成求这两种情况下，两种图的最小生成树问题.三模型假设(1)．假设货物在存放中，货物与货物之间无空隙.(2).假定货机只能沿着图中的连通路线飞行，而不走其他的路线.(3).飞机在送货期间能保持正常工作状态，不受燃料以及天气变化等影响；(4).假设飞机自身无任何故障，不考虑飞机的起飞和降落时间，认为飞机在工作时速度始终保持在平均速度为900公里/小时；(5).飞机的外形及重量的变化不影响飞机的速度；(6).飞机在送完一地货物时所剩货物不满足下一地需求时则返回；10皖西学院本科数学建模课程设计(7)

7、．假设飞机送完货后必须返回北京。四．符号说明4.1将地图上城市用点表示，并进行编号详细见下A1北京A11甘肃A2青海A12西藏A3宁夏A13重庆A4云南A14内蒙古A5新疆A15河南A6湖南A16广西A7海南A17香港A8福建A18江苏A9黑龙江A19上海A10吉林A20台湾表24.2AiAj：点Ai到点Aj的线4.3权（1）：表示题目中给出的两城市之间的权，如北京—新疆（A1A5）的权（1）为23；.4.4权（2）：表示通过两城市之间路程所花费的时间，如北京—新疆（A1A5）的权（2）为23×100÷900+2=4.55555

8、56（小时）4.5权（3）：表示通过两城市之间路程的花费，如北京—新疆（A1A5）的权（3）为23×2500+1.55×5000=65250（小时），1.15为两城市指数的平均值.4.6V：A1，A2，A3，A4，A5，A6，A7，A8，A9，A10，A11，A