基于算法的配送路线优化系统(配送系统优化论文)

中国论文网 发表于2022-12-08 14:17:12 归属于管理论文 本文已影响506 我要投稿 手机版

       中国论文网为大家解读本文的相关内容:          

论文导读:物流配送运输属于物流运输的末端运输、支线运输,具有距离较短、规模较小、额度较高等特点,一般使用汽车做运输工具。
关键词:多回路,配送,线路优化

  物流配送运输属于物流运输的末端运输、支线运输,具有距离较短、规模较小、额度较高等特点,一般使用汽车做运输工具。由于配送用户多,一般城市交通路线又较复杂,因此配送线路的选择对于降低物流成本、提高物流效率至关重要。研究如何合理规划送货线路对物流企业具有重要意义。
  一、多回路分送式配送模型的构建
  配送问题的难点就在于根据配送中心车辆的数量、能力,送货地点的数量、距离、需求量等信息,确定用哪些车辆为哪些客户送货,怎样安排每辆车的配送线路。假设在一笔业务中,配送中心经理共收到了12个客户的订单,该物流中心拥有同等规格运输车辆8辆,每辆车最大载重4吨。假定配送中心及各客户间可以互相到达,配送车辆性能相同,且运输中不考虑体积限制。
  配送过程要实现的目标可能有多个:运输线路最短、运输时间最省或总运输成本最低等。在多数情况下,运输成本和运输距离正相关,配送问题的最优目标要视实际情况而定。当业务量较小时,配送中心看重运输成本,最优目标设置为距离最短;当的业务量较大时,则更看重运输效率,最优目标设置为时间最短。
  二、距离最短的最优配送线路分析
  对于这一类问题,配送中心经理需要首先要确定派出配送车辆的数量,配送车辆的数量越少,配送成本就越低。然后确定每一辆车要服务的客户,即把客户分为若干组,分别由不同的配送车辆完成配送。最后根据每一组客户的实际位置确定每一辆车的最短配送线路。
  1、配送车辆的确定
  根据客户需求信息计算所有客户的需求总量,按照配送中心运输车辆的载重情况选择配送车辆,通常使选中配送车辆总的最大载重量略大于总需求量。由于本例中配送车辆规格相同,也可以直接用客户总需求量除以车辆最大载重量,一般取比商值略大的整数来作为派出配送车辆的数量。
  2、客户的分组
  采用扫描算法对客户进行分组。首先根据配送中心和客户之间的相对地理位置,建立以配送中心为极坐标原点,以任意一个方向为极轴正方向的极坐标系,同时把所有客户按地理位置转换为极坐标表示,需求信息注在客户旁边。然后,从最小角度的客户开始,按逆时针方向旋转,将客户逐个并入一个组,直到该组客户的需求总量超过车辆额定载重量的80%,接近车辆最大载重量为止。结合本例,分组情况如图1所示。
   图中V0代表配送中心,V1,…,V12代表12个客户,首先可以确定客户的总需求量为15.2,判定该公司需要派出4辆车完成配送任务。采用扫描算法,用从V0发出的虚线将客户分为:V1、V2、V3;V4、V5;V6、V7、V8、V9、V10;V11、V12四组,每组客户各用1辆车服务。
  3、车辆配送线路的确定
   经过分组后,问题就变成寻找4条从配送中心出发环游各组客户再返回配送中心的最短Hamilton回路,可以采用最近插入法来确定。由于确定回路的难度随回路中顶点数量的增加而增大,这里选择顶点数最多的第三组做示例,即寻找一条从V0出发环游V6、V7、V8、V9、V10再回到V0的最短Hamilton回路。
  用图2表示配送中心和各客户之间的线路关系,V0、V6、V7、V8、V9、V10为顶点,分别表示配送中心和各客户,顶点间的连线表示两者之间的线路,连线旁边的数据表示线路距离,单位:Km。
  最近插入法的基本步骤:
  步骤1:取V0作为整个Hamilton回路的起点,同时找出一个离V0最近的顶点Vk,形成一个子回路:V0→Vk →V0;
  步骤2:在剩下的顶点中寻找一个离已有子回路中的各顶点最近的顶点Vs,并在已有的子回路中找出一条边(Vi,Vj),使得Wis+Wsj- Wij最小,然后把顶点Vs插入到顶点Vi和Vj之间,用两条边(Vi,Vs)和(Vs,Vj)代替原来的边(Vi,Vj),形成一个新的子回路:V0→…→Vi→Vs→Vj→…→V0(Wij表示结点之间的距离);
  步骤3:重复步骤2,直到所有的顶点都加入到子回路中,得到的回路就是一个距离最短的Hamilton回路。
  根据最近插入法,可以依次将V7、V6、V10 、V9、V8插入子回路中,最终形成的最短Hamilton回路如图粗线所示,路线为:V0→V7→V8→V10→V9→V6→V0,最短距离为41 Km。当然,配送中心也可以如法确定另外三组客户的最短配送线路。
  三、基于时间最短的最优配送线路分析
  以往的配送业务中只重视配送距离,然而对于城市运输,车流量大,交通拥堵现象时有发生,距离短未必运输时间就短。现代配送中逐渐开始关注车辆的配送时间,距离最短不再是决定利润的唯一标准。配送中心的运营观念正在从“距离定成本”向“时间换利润”转变,因此配送中除了要考虑距离外,还要考虑效率。用最短的时间完成配送任务,从而多承担配送业务,最大限度地提高车辆的使用效率,为配送中心创造更多财富。
    时间最短的配送线路分析方法和距离最短的分析方法类似,前两步完全相同,第三步也可以使用最近插入法进行处理,只是顶点间连线的数据不再表示距离,而用各线路的平均通过时间代替,平均通过时间可以根据配送中心运行的经验确定,寻找一条使总通行时间最短的Hamilton回路。
  仍以第三组客户为例进行分析,用图3表示配送中心和各客户之间的关系,连线旁边的数据表示线路的平均通过时间,单位:min。,根据最近插入法,依次将V7、V6、V10 、V9、V8插入子回路中,最终形成的最短Hamilton回路如图3粗线所示,路线为:V0→V8→V10→V9→V6→V7→V0,配送距离为45 Km,最短时间为63min。相对于最短距离配送线路,尽管多走4 Km,但时间却节省11分钟,时间缩短了近15%。
  四、模型的评价
  在物流配送中,经营者大多是按照经验去设计送货线路及送货量。本方法运用满载率原理,采用扫描算法对客户进行合理分组,再通过最近插入法对线路进行优化,得到最优配送线路,方法简便,对物流配送工作具有较强指导意义。物流公司或其他企业都可以使用本方法来提高自己的送货效率,降低送货成本,提高市场竞争力。
  但是,该方法没有考虑跨区送货的情况,因此还可以通过考虑跨区域送货对本模型做进一步的优化。另外,本方法是基于静态的线路规划,要求客户的订货量必须是确定的,如果订单数量发生变化,那么企业决策者就要根据客户需求,对客户重新分组,再规划配送线路。

参考文献:
[1] 李念祖. 物流运筹学基础[M].北京:中国物资出版社.,2006.
[2] 方世昌. 离散数学[M]. 西安:西安电子科技大学出版社.,2003
[3] 那向明,安向丽,杨银海.送货线路问题优化研究.统计教育[J],2008,9:41-43
[4] 王勇,池洁.物流配送线路及配送时间的优化分析.重庆交通大学学报(自然科学版)[J],2008(8)
[5] 高鹏,徐瑞华. 物流配送线路优化的改进遗传算法研究.交通运输系统工程与信息[J]. 2006(6),120-124

  中国论文网(www.lunwen.net.cn)免费学术期刊论文发表,目录,论文查重入口,本科毕业论文怎么写,职称论文范文,论文摘要,论文文献资料,毕业论文格式,论文检测降重服务。

返回管理论文列表
展开剩余(