多回路分送式配送优化研究(图文)

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

　　物流配送运输属于物流运输的末端运输、支线运输，具有距离较短、规模较小、额度较高等特点，一般使用汽车做运输工具。由于配送用户多，一般城市交通路线又较复杂，因此配送线路的选择对于降低物流成本、提高物流效率至关重要。研究如何合理规划送货线路对物流企业具有重要意义。
　　一、多回路分送式配送模型的构建
　　配送问题的难点就在于根据配送中心车辆的数量、能力，送货地点的数量、距离、需求量等信息，确定用哪些车辆为哪些客户送货，怎样安排每辆车的配送线路。假设在一笔业务中，配送中心经理共收到了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