冷链车辆统一调度平台的优化设计方案讲解.doc

“郑 明 杯” 第 五 届 物 流 设 计 大 赛 题目： 冷链车辆统一调度平台的优化  冷链车辆统一调度平台的优化设计方案 前言 1.1郑明公司简介 上海郑明现代物流有限公司于2011年5月正式成立。其前身是1994年成立的上海郑明汽车运输有限公司。深耕于冷链物流领域的上海郑明现代物流有限公司初创至今已走过20年的历程，由单一的冷链运输商已华丽转型为将商流、物流、信息流和资金流整合为一体的供应链集成商，正朝着领先的专业供应链解决方案提供商迈进。50%的增长速度在中国物流业中迅速崛起。 式中， 其中，给出约束条件，每一辆车只可以完成一项请求，因此第一个约束条件为: 同时，给出第二个约束条件，由于每项请求只能由一辆车完成，所以第二个约束条件表述为: 采用矩阵表示如下：Min(f)=cx AX=1,X≥0 满足上述条件的一个可行解x..可以表示为矩阵形式: 其中，xij表示为解矩阵，满足上述条件的解矩阵每一行有且只有一个元素为1，其余元素为0。它的每一列也有且有一个元素为1，其余元素为0 。 4.2模型求解算法 本文采用了匈牙利算法来求解上述数学模型，该算法的主要思想是尽量调整效率矩阵C的元素，这样使得新的效率矩阵c’,,和c仍旧是等效的，并且c’的每一行和每一列至少有一个零元素，要重要的是没有负的元素，调度问题需要的解仍旧是相同的。 采用匈牙利法求解主要步骤如下: 1)首先变换系数矩阵，使每行每列都出现0元素，从系数矩阵的每行每列减去该行或者列的最小元素，再从所得矩阵的各列(行)减去该列(行)的最小元素，使得出新系数矩阵。 2)进行行列检验：对新系数矩阵找不同行，不同列的0元素。首先从含0元素最少的行开始，圈出此行的一个0元素，同时划去与该0元素同行或同列的其它元素0元素。然后对余下部分重复这一做法，直到查完各行。所有带圈的0元素便是最大数目的不同行，不同列的0元素，如果带圈0元素恰有n个，则这些元素的行，列下标数偶便构成原问题的最小分派。求解过程至此结束，如果带圈0元素少于n个。 3)做出覆盖所有0元素的最少直线集合。具体方法是(1)对没有圈的行打V号。(2)对打V行中所有0元素的所在列打V号。(3)对打V列中带圈元素的所在行打V号。(4)重复(2) (3)两步，直到得不出新的打V行，打V列，(5)对无V号的行画横线，对有V号的列画纵线。这样得出的直线全体，便是能覆盖所有0元素的最少直线集合。 4)变换矩阵。以得出新的0元素，从未被直线覆盖的部分找出最小元素，然后从未画直线的行减去此最小元素，并从画直线的列加上此最小元素，得出新的系数矩阵，然后，返回第二步。 4.3仿真结果分析 在MATLAB7. 0环境下完成的，验证本文算法的实验结果。由表1的结果可以看到，车的行驶距离乘上车每公里的运输成本量一般等于车辆的运输成本。当调度车型不能满足该成本时，则可以考虑换车辆类型，车辆的运输成本如表1所示。 表1调度车辆与请求任务的距离 车辆 任务 1 2 3 4 5 6 7 8 9 10 A 10 20 15 19 30 5 18 16 13 12 B 4 12 8 9 16 20 22 17 9 6 C 3 5 12 9 16 25 6 8 11 8 D 13 21 8 14 9 16 31 6 21 12 E 15 23 24 9 18 5 21 13 9 12 表2车辆的运输成本 车辆 任务 1 2 3 4 5 6 7 8 9 10 A 30 80 ∞ ∞ 120 15 72 48 ∞ 48 B 12 48 16 18 64 60 88 51 18 24 C ∞ 20 ∞ ∞ 64 ∞ 24 ∞ ∞ 32 D 39 84 ∞ ∞ 36 48 124 12 ∞