资源描述：
《送货路线优化建模论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、摘要：本文巧妙地解决了由网购的普及而造成物流行业的兴盛的情况下，送货员如何以最快的时间，最短的路线在规定时间内将货物送达的最优运行方案的问题。这属于一个典型的粧销员回路问题，该问题解法众多，本文紧扣题目，合理假设，通过最小牛成树法建立了一系列模型，为较准确的分析和评价各种送货方案并确立最优方案捉供了科学的依据。本文首先建立了将1〜30号货物送达指定地点并返回的分析和评价模型。文中使用最小生成树法的改进模型，采用单一目标规划问题，対路程进行优化，经过计算分析评价，结果显示：在将货物送到规定的地点时，可以得到一个最优化送货方式。本文
2、随后给出了在有时间限制的情况下，所给货物在指定地点指定时间内送到的最优化路线，模型屮既耍考虑路线最煎，又耍在规定的吋间范围为将货物送到。釆用多冃标规划问题模型。由于所给题目中不要求送货员返回仓库，所给数据不多，可根据第一问所给最短路径进行综合分析评估,得出如卜结论：送货员在规定的时间内对以把货物送到，并走的路线达到最短，即实现了近似最优化。本文接着建立了将100件货物分别送到50个地点的送货方案分析和评估模型。对于此问题，我们在对问题一的基础上，把货物扩展到100件即可，川最小生成树法分三区并分组求出最佳送货路线，得出的结论可以
3、很好的符合此问题的要求。纵观全文，文章详细的讨论了分别在不同的货物件数，以及有时间限定的情况下的各种评价指标，在对得出的数据进行分析评估Z后可以很好的确立送货员最佳路线方案。关键字：最佳路线时间路程最小生成树法一•问题重述1.1问题背景现在社会网络越来越普及，网购己成为一•种常见的消费方式，随之物流行业也渐渐兴盛，每个售货员需要以最快的速度将货物送达，而且往往一个人送多个地方，为了便于工作的顺利进行，需耍我们设计一个方案使其耗时最少的方案。题冃中给出了一个实际的问题，并给出了地形示意图及各点连通图，且送货员只能沿着这些联通路线行
4、走。各货物的和关信息见下表。我们需要综合起来上述问题，进行分析评估最优化。并对该实际问题给出合理的配置方案。现在的问题如门①己知送货人员的最大载重为50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时，每件货物按交接按3分钟计算，多件货物也按每件3分钟计算。则现在要求将1〜30号货物送到指定地点并返回，设计最快完成路线与方式，给出结果，要求标出送货货路线。②假定该送货员从早上8点开始送货，要将1〜30号货物的送达时间不超过指定时间，设计最快完成路线及方式，标出送货路线。③不考虑货物时间设定，现在要将100件货物，
5、全部送到指定地点并返回。送货员可中途回來取货。设计最快路线与方式，标出送货路线和给出所冇送完快件的时间二.问题的假设对于上述实际问题，我们给了合理的假设：（1）假定目前该市内的所有连接道路均可以顺利通过，即不岀现堵车悄况，且路而条件均和同；（2）送货员在所有路线上的速度恒定，即道路的的1111折，转弯等不会对车速产牛影响；（3）对于某些至少耍经过两次以上的送货地点，认为仅在第一次经过吋停留，即每第一次经过吋就把所有货物一次性送到；（4）在每到达一送货地点后停留时间一定，不会岀现特殊情况而延课时间；（5）同一地点有多种货物时按一种
6、货物停留的时间算即目的地只停留三分钟。三.参数的假定0:每次送货路线的总长度；4•表示每两点之间的最短路径；5:i=（1,2,3）所限制的货物总重量的相对误差：6:i=（1,2,3）所限制的货物体积的相对i吴差；xi:xi=Oorl（0-1规划模型）;匕・=（123）：送货货物的总体积;/■:有时间限制卜•送货路线所需要的时间；t:无时间限制下送货路线所需要的时间v/:i=(1,2……,50)=(1,2,3):送货货物的总重量;每件货物的体积；m,；/=(l,2,・.・・・,50)每件货物的重量；厶：i=1,2,3第三问中每次送
7、货的总路线二.模型的建立与求解在路线中，每个目的地看作图中的一个节点，各目的地之间的路看作图中连通节点的边，齐条路的长度或行驶时间看作对应边上的权所给的线路网就转化为加权网络图，而所求问题就转化为在给定的加权网络图屮寻找从给定点O岀发行遍所有顶点至少一次再冋到O点，使得总权即时间最短。对于第一道题前三十个货到达的目的地的节点看作点集V,连接任意两点的路线所需时间作为权值赋给对应边，形成边集E得到加权图G(V,E)(因为32和38两地点通过35的路线比其他路都短所以可以两点直接连起而权值为32T35T38的权值和)。算法一：我们可
8、以采用最小生成树法算岀0点到任意一点的最短距离，然后根据最短路线逐次加边加权得到从0点出发冋到0点的最短路线。问题一若将1—30号货物送到指定地点并返回设计最短时间路线方式一.问题分析将1-30号货物送到指定地点并返回要求最短时间；经计算得前30号货物的重量是M
