5.1.9哈密尔顿圈[6]模型求解货车最短行驶路线
送货员要将货物送到七个卸货点（加上配送中心共八个点）并返回，即经过其中每一个点刚好形成一个圈。对于这种情况设计它的最短路线问题，我们建立哈密尔顿圈模型。
哈密顿图（Hamiltonian path）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路，含有图中所有顶的路径称作哈密顿路径。 一、对于这一模型我们开始要画出8个点的坐标图，结合图形便于模型的求解和优化。
图4 区域①送货地点的坐标图
8
1
4
6
2
7 3
5
二、任取初始哈密顿回路:C1?[1 2 3 4 5 6 7 8];
对所有的i，j，1?i?1?j?n，若W(Vi,Vj)?W(Vi?1,Vj?1)?W(Vi,Vi?1)?W(Vj,Vj?1)，则在C1中删去边?Vi,Vi?1?和?Vj,Vj?1?而插入新边?Vi,Vj?和?Vi?1,Vj?1?，形成新的H圈C，即
C?[V1,V2,V3????Vi,Vj,Vj?1,????Vi?1,Vj?1,????Vn]，V1对C重复这一步骤，直到条件不满足为
止，结合图一的路线图观察，从而进行优化，使用这种方法，借助matlab编程使用迭代的方法可以求出它的最优路径（见附录程序）。 综合上述方法，可求：
最短路线：8?1?2?4?6?7?5?3?8 最短路程：84.4332KM。 最短运货用时为2.11小时。
图5 区域①货物的最佳路线图
15
5.1.10设计车辆调度方案
上述，我们已经解决了某个区域的供货方式和行驶路径问题，以下我们做出整体的配送方案。
1.根据货物的每日和每周的需求量，我们做以下安排，当当日运送量Q远小于一辆货车的载货量（5180箱）的，由相邻区域安排货车同时运送两个区域的货物或者积压货物到一周之内运送，我们其他情况则为一个区域单独安排车次M，保证货物尽快送到。粗糙模型时，货物运送采用一周统筹的方式。
M=Q/5180 (四舍五入) （14）
2..车次不代表安排货车的数量，同一辆货车一天可以走多个车次。每日货车行驶车次N需要根据计算货车行走某一路线（一个车次）所需的时间T来设定。已知司机每日工作八小时。 N=8/T (取整法) （15）
3.货车数量确定后，则可分别安排每辆车的负责区域，尽量保证几辆车的行驶时间和行驶车次相等。
表9 各区域车次安排 周1车周2车周3车周4车周5车周6车周总车区域 任一天 次 次 次 次 次 次 次 A 4 4 3 4 0 0 0 15 B 0 0 0 1 1 0 0 2 C 2 1 1 0 1 0 0 5 D 2 2 2 2 1 0 0 9 E 0 1 1 0 1 0 0 3 F 1 0 0 1 1 0 0 3 G 1 1 0 0 1 0 0 3 H 0 1 0 0 0 0 0 1 I 0 1 0 0 0 0 0 1
16
J K L M N O P Q R S T 合计 0 0 2 0 1 0 1 2 5 3 4 28 1 1 1 0 0 1 2 3 2 2 3 27 0 2 1 1 0 1 0 1 1 3 2 19 1 0 2 1 1 0 1 2 5 1 3 25 0 1 0 0 0 1 0 1 1 4 1 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 6 2 2 3 4 9 14 13 13 112 一、粗糙模型
1、通过步骤5.1.4我们已知每个区域所需的车次数量，以及总车次数为112。根据以上结果，最近的区域出一个车次需要2.11小时，我们近似估计行驶一个车次平均需要的时间为4小时。按每个司机每天行驶8小时，每天行驶2个车次，则每辆车一周可以行驶16个车次计算，需要7辆车分送所有的货物。
进一步考虑到货车到卸货点卸货花费的时间，货车修理和司机轮休的影响，我们安排15辆车来进行运送。
将图中20个统筹区分为5部分，每3辆货车分管一个部分，均匀送货，具体情况参照步骤5.1.4中的车次表。
2、若所有货物都必须当天送达，则无论货物多少都要出车，仍按每辆车一天行驶2个车次计算，表中给出周一最繁忙需要出28个车次，即公司要安排14辆车。可以看出之前我们安排总共15辆车的计划是合理的。
二、最终配送方案
下面给出车辆的具体较优调度方法和运输公司所需拥有的最少车数。
由于对全部给定区域内的所有点进行优化统筹过于繁杂，但若是只考虑全局中的一小块又会失去统筹规划的意义，为此我们对题目给定范围进行扇形分区。总共划分为10个区域。则对于每一块区域，其总的货物需求量为它所包含的所有用户的货物需求量之和。货物由配送中心运至该区域的平均时间由于考虑到用户利益优先，最远点保证送到的原则，定为到其中较远点的距离。则有配送中心分别到各区域所需要的时间和各区域的货物需求量如下表：
表10 配送情况表 区域 到货时间 需求量
17
A 8h B 8h C 5h D E F G H 4h I 6.5h J 8h 4.4h 2.3h 3.5h 3.5h 7477件 74100537061230413169件 件 件 件 4088714439332301021111586件 件 件 9件 1件
优化调度方案所要达到的目标是所需的车辆数最少，所需发车的车次数最少。车辆的总闲置时间最少，以及车辆的总剩余可载货空间最少。
经多次试验（穷举法）得到一种较优的调度方案，见下表： 表11 调度方案表 星期 目的地 星期一 星期二 星期三 星期四 星期五 星期六 星期日 车辆 小车1 小车2 小车3 小车4 小车5 小车6 小车7 小车8 中车1 大车1 F,H B J J J I I I B,E A F,H B J J J I I I D,G A F,H B J J J I I I D,G A F,C B J J J I I I C,F A B B J J J I I I F,H A H,H B J J J I I I I A B B J J J J J A I A 经分析知此方案所有车辆均没有闲置时间，车辆总数仅需10辆，总的剩余可载货量仅有4000件左右，发车次数也仅有80车次，是一种较优的调度方案。
18
5.2 对问题二的求解
问题二中，我们需要在原图中再安置5个配送中心，从而使配送更快捷，服务更优化，使目标函数取得最优解。
5.2.1 确定八个待定的配送中心坐标
首先我们利用excel对数据进行合并，利用经纬度分割的方法，使16764个用户位置聚合到100个用户聚合点（每个区域的中心位置）。并用三维图进行表示，其中坐标x,y代表100点的经纬度，坐标z表示某个点的货物总需求量，如下图所示。
图6 用户需求三维图
从图中可以看出，有明显的货物量凸起的部分，为货物紧需区域。我们利用matlab筛选出局部最优点，给出八个待定的配送中心位置，即需要从这八个点中进行选择。 八个待定配送中心的位置如下：
表10 待定点信息 待定点编号 经度 纬度 1 2 3 4 5 6 7 8 107.7914972 108.1980758 108.0568015 108.679651 108.6892185 109.2116693 109.1749773 107.757158 26.22478355 26.22357626 26.71716445 26.9668901 25.9739482 26.89589863 26.1636702 26.65597414
在matlab中绘制二维图可以看出八个待定点的位置如下：
19