百源木业有限公司配送线路优化(4)

3.3 扫描算法

扫描算法（Sweep Algorithm）也是用于求解车辆数目不限制的VRP问题，与节约算法不同的是，它属于亚启发式算法，而节约算法属于构造算法。

3.3.1 扫描算法的基本原理

扫描算法是一种“先分组后路线”的算法。所谓分组，即指派给每辆车一组点。一种简单的分组方法是将以配送中心为原点的坐标平面划分为多个扇形区域，并初步将每个扇形区域的点分派给一辆车，然后扩充路线。如果在进行了一次“分组-路线”的路线构造后，还存在未分配点，则再进行“分组-路线”程序。如此反复，直到所有的点均已分配为止[10]。 3.3.2 扫描算法的主要步骤

（1）以起始点0点作为极坐标系的原点，并一连通图中的任意一顾客点和原点的连线定义为角度零，建立极坐标系。然后对所有的顾客所在的位置，进行极坐标变换。

（2）分组 从最小角度的顾客开始建立一个组，按逆时针方向，将顾客逐个加入到组中，直到顾客的需求总量超出了负载的限制。然后继续建立一个新的组，继续按逆时针方向，将客户加入组中。

（3）重复（2）中的过程，直到所有客户都被分类为止。 （4）路径优化 对各个组内的单回路进行路径优化[11]。

3.4改进后的最近插入法

TSP模型是单回路运输问题的最为典型的一个模型，它的全称是Traveling Salesman Problem1，中文叫做旅行商问题。它是一个典型的NP-Hard问题，对于大规模的线路优化问题，无法获得最优解。最近插入法就是一种解决此问题的启发式算法。

9

3.4.1 最近插入法

最近插入法是Rosenkrantz和Stearns等人在1977年提出的一种用于解决TSP(旅行商)问题的算法。最近插入法由四步完成：

（1）找到c0i最小的节点vi，形成一个子回路（subtour），T??v0,vk,v0?。 （2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点vk。 （3)在子回路中找到一条弧（i，j）,使得cik+ckj-cij最小，然后将节点vi插入到节点vi，vj之间，用两条新的弧(i，k)，（k，j）代替原来的弧（i，j），并将节点vk加入到子回路中。

（4）重复步骤（2）、（3），直到所有的节点都加入到子回路中。 这样，子回路就演变为了一个TSP的解[12]。

由于最近插入法解决的是单回路运输问题，故笔者在此方法基础上进行改进和修正，使其能解决多回路运输VRP问题。有改进的方法如下： 3.4.2 改进的最近插入法

（1）找到c0i最小的节点vi，形成一个子回路（subtour），T??v0,vk,v0?。 （2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点vk。若此时回路的总货运量未超过车的载重限制，则继续步骤（3）。否则，转（1）寻找新的一条回路。

（3）)在子回路中找到一条弧（i，j）,使得cik+ckj-cij最小，然后将节点vi插入到节点vi，vj之间，用两条新的弧(i，k)，（k，j）代替原来的弧（i，j），并将节点vk加入到子回路中。若此时该回路的总路程为未超过车辆的行程限制，则继续步骤（4）。否则转步骤（1），寻找新的一条回路。

（4）重复步骤（2）和（3），直到每一个节点都被归入某一个子回路中。

10

第4章 百源木业有限公司配送路线优化研究

4.1 建立VRP模型

多回路运输问题时现实生活中十分常见的一种调配问题。此类调配问题的核心问题是车辆调度。因此VRP模型也应运而生，成了解决多回路问题的一个相当成功的模型。据此对百源木业有限公司的配送系统建立VRP模型。

基本条件：百源木业公司需给9个客户送货，客户依次为1，2，?,9，现有1辆7吨（长7.8m,宽2.2m,高3.6m）的货车（每百公里油耗21L），2辆11吨(长9.5m,宽2.3m,高3.6m)的货车(每百公里油耗27L)，柴油每升7.07元，司机每天工资100元。

模型目标：确定所需要的车辆的数目N、车辆类型、司机数量以及各车行走的路径，并指派这些车辆到一个回路中，同时包括回路内的路径安排和调度，使得运输总费用最小。

限制条件：

（1）基于人性化与安全的考虑，当运输里程超过350公里时，需配备两名司机，为防止突发运输事件，车辆必须当天回到公司，减去去由于装卸货等影响因素，各车最大运输距离为600公里。

（2） 每辆车完成任务之后都要回到源点0处。

（3） 车辆的容量限制不能超过。7吨的货车最多可装300张细木工板，11吨的最多可装500张细木工板。11吨货车运输单价比7吨的低，优先使用11吨车，若不超过300张细木工板，则使用7吨货车。

4.2百源木业公司的配送线路的分析与优化

已知百源木业公司为0点，分别向9个小客户点配送细木工板，其拥有一辆7吨的车和两辆11吨的车， 7吨卡车最大容量为300张细木工板，11吨卡车最大载量为500张。设各点间的距离为C,C??cij|i,j?1,2每辆车的载货量为ri，各点需求量为Ri?i?1,211

,9?，节约距离为?cij。

,9?，每辆车的行驶里程为

Li?i?1,2,9?，Li?600且公里，婺源为0点，客户点1，2，?，9。

各县市的细木工板运量和配送距离如表2所示。

表4-1 运输任务表 客户 货运量（张/周） 配送距离（km） 75.9 89.2 186.7 170.3 57.0 153.8 87.0 81.5 82.5 180 120 120 60 80 220 70 90 200 1景德镇 2乐平市 3鹰潭市 4贵溪市 5德兴市 6上饶市 7常山县 8开化县 9黄山市

4.2.1 原配送线路基本数据分析

目前，百源木业有限公司对小客户公司采用的配送模式如图2所示。各配送线路低得里程，所需司机数量及工资的基本情况如表3所示。

表4-2 配送信息表

路线 0-1-2-0 0-3-4-0 0-5-6-0 0-7-8-0 0-9-0 运距 213.7km 373.4km 315.4km 202.7km 165.0km

由上表可知，公司每周需7吨货车5车次配送，司机6人次，所需工资600元，运输总里程为1270.2千米，消耗的柴油266.75升，所需燃油费1885.87元，一共花费2485.87元。

运货量 300 180 300 160 200 车型 7吨货车 7吨货车 7吨货车 7吨货车 7吨货车 司机 1 2 1 1 1 12

4.2.2 基于节约算法的企业配送路线优化

首先，确定各县市间的最短距离，县市间最距离表4所示。

表4-3 各县市间最短距离表 （单位：千米）

县市 0婺源县 1景德镇 2乐平市 3鹰潭市 4贵溪市 5德兴市 6上饶市 7常山县 8开化县 9黄山市 0婺源县 0 1景德镇 75.9 0 2乐平市 89.2 48.6 0 3鹰潭市 4贵溪市 5德兴市 57.0 86.1 48.6 125.0 107.2 0 6上饶市 153.8 7常山县 87.0 8开化县 81.5 9黄山市 82.5 154.7 170.5 268.7 251.3 103.1 232.0 126.8 91.4 0 186.7 170.3 157.1 173.8 97.3 0 117.0 16.4 0 194.3 161.2 148.9 143.1 158.1 156.4 98.5 81.5 170.2 206.3 153.9 190.1 98.3 115.7 34.2 0 104.6 103.2 0 83.3 0 数据来源：谷歌地图

然后，形成一初始解，，令Ii??i?，?i?1,2,9），且

i=1，最短路径Li?2c0（?，,9?，iLi?600公里，载货量ri?Ri，且ri?500，对9个客户点进行标记?B9?0，且Bi?2。

B1?B2?其次，求节约里程。根据最短距离表，根据式（1）计算出用户间的节约里程,并由大到小排列，编制节约里程?cij顺序表，如表5所示。

13

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库百源木业有限公司配送线路优化(4)在线全文阅读。