2、 问题分析
送货路线问题可以理解为:已知起点与终点的图的遍历问题的合理优化的路 线设计。
图的遍历问题的指标:路程与到达的时间,货物的质量与体积,以及最大可以 负载的质量与体积。在路线的安排问题中,考虑所走的路程的最短即为最合理的 优化指标。
对于问题二要考虑到所到的点的时间的要求就是否满足题意即采用多次分 区域的假设模型从而找出最优的解
模型二 —对于问题一的求解
数学建模_送货线路设计问题
2、1 模型的建立 由前 30 件货物可以到达的地点可以知道 i,j= 13、14、16、17、18、21、23、 24、26、27、31、32、34、36、38、39、40、42、43、45、49。
图 2 需要达到的点(红点标注的)
其中共经过 21 个点,运送 30 件货物 该 30 件货物 =47、3kg<50kg =0、8371 ,所以可以一次把货物携 带进行运送。 由 T 与 W 关系可知要使所用的时间最小即所走的距离最短。即
假定送货员最大载重 50 公斤,所带货物最大体积 1 立方米。送货员的平均速 度为 24 公里/小时。假定每件货物交接花费 3 分钟,为简化起见,同一地点有多件 货物也简单按照每件 3 分钟交接计算。 现在送货员要将 100 件货物送到 50 个地点。请完成以下问题。
1、 若将 1~30 号货物送到指定地点并返回。设计最快完成路线与方式。给 出结果。要求标出送货线路。
的 inf)。
但 dijkstra 算ห้องสมุดไป่ตู้只能求出从结点 i 到其它各结点的最短路径。算法引入这样
两个集合 s 与 t,s 就是那些已经确定了到 i 结点的最短路径的结点,t 为全集 u
与 s 的差集,即那些还未确定最短路径的结点。而且 s 的初值就是{i},t 的初值
就是 u-{i}。另外再引入一个标记数组 d[n],其中在某一步 d[k]表示当前从 i 到
3、2、符号说明
数学建模_送货线路设计问题
其中 i,j=1、2、3……50 并且 M=50kg
V=1
4、 模型的建立及求解
模型一
模型二
模型三
模型四
最短路 径模型
图的遍 历模型
多区域 最短路
多阶段 最短路
任意两点 之间的最
模型一 由 起 始 点
遍历路径
多区域无 返回起点
多阶段有 返回起点
短路1、距1离模型的建立 回到原点
2、 假定该送货员从早上 8 点上班开始送货,要将 1~30 号货物的送达时间不 能超过指定时间,请设计最快完成路线与方式。要求标出送货线路。
3、 若不需要考虑所有货物送达时间限制(包括前 30 件货物),现在要将 100 件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路, 给出送完所有快件的时间。由于受重量与体积限制,送货员可中途返回取货。可 不考虑中午休息时间。
数学建模_送货线路设计问题
送货路线设计问题
1、 问题重述
现今社会网络越来越普及,网购已成为一种常见的消费方式,随之物流行业 也渐渐兴盛,每个送货员需要以最快的速度及时将货物送达,而且她们往往一人 送多个地方,请设计方案使其耗时最少。
现有一快递公司,库房在图 1 中的 O 点,一送货员需将货物送至城市内多处, 请设计送货方案,使所用时间最少。该地形图的示意图见图 1,各点连通信息见表 3,假定送货员只能沿这些连通线路行走,而不能走其它任何路线。各件货物的相 关信息见表 1,50 个位置点的坐标见表 2。
对于问题三则要考虑到体积与质量的双重影响,每次到达后找到达到最大的 体积与质量的点然后返回,再依次分析各个步骤中可能存在的不合理因素达到模 型的进一步合理优化得到最合理的解。
3、 模型假设与符号说明
3、1、模型的假设
(1)、到同一地点的货物要一次拿上,即不考虑再以后又经过时再带些货物 (2)、要求达到不超过的时间不包括此次在该点交易的时间。 (3)、所用的距离数据都精确到米而时间则精确到 0、0001h (4)、同一地点有多件货物也简单按照每件 3 分钟交接计算。
使用循环的结构求出 1-50 各个点之间的最短距离。程序 1 见附录 2、1 可以求出 w 与 a
a 为最短路径就是的所过的的地点 如从 O 开始到其余 50 个点的 a(0)=[ 0 7 4 8 3 15 1 18 12 14 18 13 13 18 21 12 23 21 0 24 22 0 29 17 31 19 0 31 30 25 22 26 23 28 31 38 21 40 36 27 34 37 43 38 41 36 41 40 46 42 40] 要从 O 点到 16 点则要先到 23 即 0-23-16 要从 O 点到 23 点则要先到 17 即 0-17-23-16 要从 o 点到 17 点则要先到 21 即 0-21-17-23-16 而 O 可以直接到 21 所以从 0 到 16 的最优路径就是 0-21-17-23-16 最短的距离就是 w(0,16)=7493m
３、 算法结束,此时 d[k]中保存的就就是从 i 到 k 结点的最短路径。 算法就以这样非常简单的形式完成了求解,时间复杂度就是 O(n^2),确定了从
i 到其余各结点的最短路径。 1、2 模型的求解 根据算法与相邻的点的距离可以用 dijkstra 求出任意两点的最短路径。
图 1 相邻的点的距离
的最短路
的最短路
我们为了求出各个点的之间的最短的路径,使用 Dijstra 算法求解。
Dijkstra 算法就是图论中非常有名的一个算法。
图采用邻接矩阵的形式描述,w(i,j)表示结点 i 到结点 j 间的最短距离,如果
没有直接连通,则为无穷大,计算机中可以用一个很大的数据代替(如 matlab 中
k 的较短路径,d[k]的初值为 w(i,k)。
整个算法过程如下:
１、 在 t 中选择一个 d[k]最小的结点 k,将 k 并入 s,并从 t 中去掉,如果 t
为｛｝则转到３;
数学建模_送货线路设计问题
２、 用 k 结点与 t 中其余结点进行一遍比较,如果 d[i]>d[k]+m[k][i],则用 d[k]+m[k][i]取代原来的 d[i],重复１;