快递员的送货策略问题

  • 格式:doc
  • 大小:612.00 KB
  • 文档页数:27

快递员的送货策略问题
摘要
在货物运输的过程中,合理的选择货物路线很重要,他不仅可以加快配送速度,提高服务质量,还可以降低配送成本,增加经济效益.本文构建货物路线的规划模型,运用图论思想,Dijkstra算法,经典Floyd算法,利用lingo与MATLAB 进行编程求解,给出了最佳的送货路线,另外将货物的分配问题转化成旅行商推销问题,进行编程求解;根据运输路线策略中的成组法,用射线旋转法进行区域划分,以送货员最大承受力为50公斤,货物体积不大于1立方米为依据,利用整体规划进行区域规划,从而得到最优化模型.
问题一以最快完成送货任务并返回仓库的路线与方式,分析题知尽可能地缩短路径可以达到尽快完成任务的目标.在题目所给的各个点的坐标基础上,为确定最短路径,先应用Dijkstra算法求解出任意两点的直线距离,运用Floyd算法,借用MATLAB求出任意两点之间的最短距离,应用lingo软件进行优化求解,求得遍历路程结果为125499.5m,时间为493.7min.
问题二在问题一的前提下进行了对送货时重量和体积的约束,经过分析,快递员需要在送货途中返回一次仓库,进行补货.根据问题一中最小生成树,根据聚集原则,将区域分成两部分,进行分次求解,第一部分路程为67554.8m,时间为261.9min ,第二部分路程为66624.56m,时间为246.8min .
关键字:Dijkstra算法;经典Floyd算法;0-1规划法;最小距离
一、问题重述
小张是某快递公司送货员,其负责送货的区域如图,该区域包含50个送货地点,仓库在图中O点处.送货时,小张只能沿图中的道路行进,没有其他道路可选.送货时,小张的平均行进速度为24公里/小时,每件货物交接时间3分钟(如同一地点有多件货物,交接时间也按每件3分钟计算).
根据某天小张的送货清单,请你们帮助他解决下列问题:
1.设计最快完成送货任务并返回仓库的路线与方式,给出结果并注明送货路线.
2.实际上小张每次送货时,只能装载重量不超过50公斤,体积不超过1立方米的货物.这样,小张不能将全天的货物一次取走,只能中途返回仓库取货.在这种情况下,设计最快完成送货任务并返回仓库的路线与方式,给出结果并注明送货路线.
以上两种情况都不考虑中午休息时间.
图1 送货地点示意图
表1:送货地点坐标
二、问题分析
在日常生活中购物送货问题,如何在有效的时间内送到货物且能最大限度的
节约成本,合理规划过程中的最短路线.我们需要在考虑题的过程中重点分析各个点的路径问题,送货员能承受的重量体积等因素条件下,规划处最优路线.首先我们利用excel处理数据,求出总重量,总体积等数据,在求出每条路的总距离,对于送货员能承受的重量等情况,我们利用射线旋转法进行划分,0-1型规划法对问题进行巧妙的转化,从而求解.
对于问题一:不考虑装载重量和物体体积,最佳运送方案就为找出一条走遍所有送货点然后返回出发点的最短路线.根据表1和表2所给出的送货点位置信息即可计算出所有直通点的距离.根据以上数据即可利用Floyd算法算出任意两点间的距离矩阵.然后运用lingo软件就可以得到最优路线.
对于问题二:由于质量和体积的约束,综合总的质量与体积得出送货员将货物的分配问题转化成旅行商推销问题,进行编程求解,根据运输路线策略中的成组法,用射线旋转法进行区域划分,以送货员最大承受力为50公斤,货物体积不大于1立方米为依据,利用整体规划进行区域规划,从而得到最优化模型.
三、问题假设
1.假设送货员只能沿如图路线图行驶,不能走其他的任何路线.
2.在联通线路中,送货员可自由选择路口.
3.交接货物只需要3分钟,行进速度总是24公里/小时,路上行进畅通无意
外阻碍.
4.如果要从任意一点出发前往另一点,送货员必然选择最短路径.
5.送货员路程中都是匀速行走.
6.不考虑送货员中午休息及中途休息.
四、符号说明
五、模型建立与求解
5.1模型分析
不考虑装载重量和物体体积,所以最佳运送方案就为找出一条走遍所有送货点然后返回出发点的最短路线.根据表1和表2所给出的送货点位置信息即可计算出所有直通点的距离.(程序见附录3)根据以上所得数据,即可采用0-1规划模型寻找送货点间的最短路径.
图2坐标点之间的关系
5.2模型的建立
利用图论思想,将已连接的送货点一一标明,送货点抽象为下列图的顶点.任意两顶点间都有通路.讲两点之间的路线权值赋为,两坐标间的距离.这样送货点的分布图就构成了加权网络图见图(2).问题就转化为在给定加权网络图中寻找从原点0出发满足做给约束条件下,行遍所有顶点,并再回到0点,使得总权最小.
设假最佳送货路线问题由送货点1,2,3…,n组成,W ij表示送货点i到送货点j之间的距离决策变量定义为:1,选择从送货点i到送货点j,
X ij=
0, 否则,。