车辆调度优化模型仿真研究

基金项目:江苏省教育厅 2010 年度高校哲学社会科学研究基金项目 (2010SJB630036) 收稿日期:2011 － 02 － 25 第 28 卷 第 9 期 计 算 机 仿 真 2011 年 9 月 文章编号:1006 － 9348(2011)09 － 0346 － 04 车辆调度优化模型仿真研究 宋维堂，张淑梅 (南京交通职业技术学院电子信息 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 系，江苏 南京 211188) 摘要:研究车辆调度优化问题，针对运输车辆的空间排放和时间安排等，要达到运输路径最短，费用最省的要求。为了实现 城市车辆优化调度，节约运输成本，同时传统的车辆调度算法存在计算复杂度高，不利于实际应用等问题，提出了一种改进 的车辆调度优化算法模型。首先对城市车辆调度建立优化数学模型，建立一种动态开放的车辆调度系统，并采用匈牙利算 法对数学模型进行求解。仿真结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明，提出的新的算法不仅能有效的求解车辆调度优化模型，而且计算机复杂度较低，计 算效率较高，收敛速度较快，验证了算法的实用性和有效性。 关键词:车辆调度;线性规划;仿真模型;匈牙利算法 中图分类号:TP391 文献标识码:B Research on Transit Routes Network Design Based on Improved Genetic Algorithm SONG Wei － tang，ZHANG Shu － mei (Nanjing Communications Institute of Technology，Nanjing Jiangsu 211188，China) ABSTRACT:vehicle scheduling problems． In order to achieve optimal operation of city vehicles，saving transport costs，while there is the traditional vehicle scheduling algorithm with high computational complexity，and other issues not conducive to practical applications，an improved optimization algorithm for vehicle scheduling models． First，the establishment of urban vehicle scheduling optimization model，the establishment of a dynamic open vehicle dispatc- hing system，and using the Hungarian algorithm for solving the mathematical model． Simulation results show that the new algorithm can effectively solve the vehicle scheduling optimization model，and the computer low complexity，high computational efficiency，fast convergence to verify the practicability and effectiveness of the algorithm． KEYWORDS:Vehicle scheduling;Linear programming;Simulation model;Hungarian Algorithm 1 引言 传统的车辆的优化调度问题一般可依据空间特性以及 时间特性来分为车辆路径规划问题与车辆调度问题。当不 考虑时间要求［1］［2］;车辆调度时只考虑时间要求安排运输线 路时称为 VSP。一般来说，车辆调度依照运输任务可以分为 纯装问题、纯卸问题的混合问题，其中装卸混合问题也是车 辆在途中的装货卸货问题。一般的，随着其车辆调度输入规 模的扩大，车辆的调度问题的求解难度就会增加。当前，目 前没有有效的多项式时间算法来求解 NP 难题［5］。常用的 算法可以分为启发算法和智能算法。启发式 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 主要分为 分支界定法等。 针对运输车辆的空间排放和时间安排等，要达到运输路 径最短，费用最省的要求。为了实现城市车辆优化调度，节 约运输成本，同时传统的车辆调度算法存在计算复杂度高， 不利于实际应用等问题，提出了一种改进的车辆调度优化算 法模型。首先对城市车辆调度建立优化数学模型，建立一种 动态开放的车辆调度系统，并采用匈牙利算法对数学模型进 行求解。仿真结果表明，提出的新的算法不仅能有效的求解 车辆调度优化模型，而且计算机复杂度较低，计算效率较高， 收敛速度较快，验证了算法的实用性和有效性。 2 车辆调度相关原理 2． 1 线性规划算法原理 线性规划是科学与工程领域应用非常广泛的数学模型， 它主要研究线性函数在不同约束条件下的极值问题。线性 规划作为运筹学的一个重要分支，线性规划问题就是在约束 条件之下，求一个线性函数的最大和最小值问题，数学表达 式描述如下［6］: —643— min = C1X1 + C2X2 + … + CnXn (1) a11x1 + a12x2 + … + a1nxn !b1  an1x1 + an2x2 + … + annxn !bn x1，x2，…，xn  { 0 (2) 其中，C1X1 + C2X2 + C3X3 + …CnXn 表示为目标函数， Cj(j = 1，…n)表示为价值函数，C表示的是价值向量，Xj(j = 1，…n)为求解变量，其由系数 aij 组成的矩阵。 A = a11 … a1n   an1 … a   nn 表示的是约束矩阵。列向量 b = b1，b2，…，b( )n T 是右端向量，而条件 xi 为非负约束。设某 个向量 x = x1，x2，…x( )n T 满足约束条件，那么称其为可行 点。 求解线性规划问题时，首先需要判别该问题属于哪一种 类型情况。 2． 2 车辆调度问题 车辆调度是线性规划问题一种，设有 m 个地点 A1， A2…An，每个地点的运输产量分别表示为 a1，a2…an，同时有 n个销售地点 B1，B2…Bn，每个销售地点的需求量分别表示 为 b1，b2…bn，Cij表示从产地 Ai运往销地Bj的单位运输费用， Xij 是决策变量，表示产地 Ai 运往销地 Bj的调运量，即车辆调 度运输问题数学表达如下［7］: min(f)= ∑ m i = 1 ∑ n j = 1 CijXij (3) s． t ∑ m j = 1 Xij = ai，i = 1，2…m ∑ m i = 1 Xij = bi，j = 1，2…n Xij  0，i = 1，2…m，j = 1，2…      n (4) 若在调度问题中没有产销平衡这一限制，当产大于销 时，(即∑ m i = 1 ai ＞ ∑ n j = 1 bj) ，则更改数学模型表示如下: 任一组变量 Xij(i = 1，2…，m;j = 1，2，…，n)的值，使其 满足约束条件: ∑ n j = 1 xij !ai(i = 1，2，…m) ∑ n i = 1 xij = bj(j = 1，2，…n) xij  0(i = 1，2，…m;j = 1，2，…n      ) (5) 并且使目标函数 S =∑ n j = 1 ∑ m i = 1 CijXij的值最小，即总运量达 到最少。 3 线性规划车辆调度算法 车辆调度问题是一种特殊的运输问题，调度问题与实际 问题结合非常紧密，调度问题涉及的主要范围在城市，所以 对路径的选择非常重要。 3． 1 车辆调度模型建立 定义在某个时段 t内，假设有m车辆调度请求任务，该车 辆调度请求的地点的坐标为(xi，yi)。首先设调度的无车辆任 务的车辆共有 i辆，在监控的中心地图上，他们的位置都会精 确的显示，设位置坐标为(xj，yj) ，所以这样在地图上就能够 获得任一辆车到任务申请地点的距离，dij 是车辆 j距离申请 位置 i的距离。 依上所述，该车辆调度模型的数学表达式为: min(f)= ∑ m i = 1 ∑ l j = 1 fij = ∑ m i = 1 ∑ l j = 1 cj* dij* xij (6) 式中，xij = 1，汽车 j调度到任务请求 i 0，{ 其他 其中，给出约束条件，每一辆车只可以完成一项请求，因 此第一个约束条件为: x11 + x12 + x13 + …x1l = 1 x21 + x22 + x23 + …x2l = 1  xm1 + xm2 + xm3 + …xml = { 1 (7) 同时，给出第二个约束条件，由于每项请求只能由一辆 车完成，所以第二个约束条件表述为: x11 + x21 + x31 + …xm1 = 1 x12 + x22 + x32 + …xm2 = 1  x1l + x2l + x3l + …xml = { 1 (8) 采用矩阵表示如下: min(f)= cx AX = 1，X 0 (9) A = 1 1 … 1 1 1 … 1  1 1 … 1 1 1 1 1 1 1    1 1 …                           1m×n列 满足上述条件的一个可行解 xij 可以表示为矩阵形式: xij = x11 x12 … x1l x21 x22 … x2l    xm1 xm2 … x   ml 其中，xij 表示为解矩阵，满足上述条件的解矩阵每一行 有且只有一个元素为 1，其余元素为 0。它的每一列也有且只 有一个元素为 1，其余元素为 0。 —743— 矩阵 c = c1d11 c2d12 … cld1l c1d21 c2d22 … cld2l    c1dm1 c2dm2 … cld   ml 称为效率矩阵，其 中，(cij)表示把车辆 j派到任务 i的运输成本。 3． 2 模型求解算法 本文采用了匈牙利算法来求解上述数学模型，该算法的 主要思想是尽量调整效率矩阵 c的元素，这样使得新的效率 矩阵 c＇和 c，仍旧是等效的，并且 c＇的每一行和每一列至少有 一个零元素，要重要的是没有负的元素，调度问题需要的解 仍旧是相同的。 采用匈牙利法求解主要步骤如下: 1)首先变换系数矩阵，使每行每列都出现 0 元素，从系 数矩阵的每行每列减去该行或者列的最小元素，再从所得矩 阵的各列(行)减去该列(行)的最小元素，使得出新系数矩 阵。 2)对新系数矩阵找不同行，不同列的0元素。首先从含0 元素最少的行开始，圈出此行的一个 0 元素，同时划去与该 0 元素同行或同列的其它元素 0 元素。然后对余下部分重复这 一做法，直到查完各行。所有带圈的 0 元素便是最大数目的 不同行，不同列的 0 元素，如果带圈 0 元素恰有 n个，则这些 元素的行，列下标数偶便构成原问题的最小分派。求解过程 至此结束，如果带圈 0 元素少于 n个。 3)做出覆盖所有 0 元素的最少直线集合。具体方法是 (1)对没有圈的行打√号。(2)对打√行中所有0元素的所 在列打√号。(3)对打√列中带圈元素的所在行打 √ 号。 (4)重复(2) (3)两步，直到得不出新的打 √ 行，打 √ 列， (5)对无√号的行画横线，对有√号的列画纵线。这样得出 的直线全体，便是能覆盖所有 0 元素的最少直线集合。 4)变换矩阵。以得出新的 0 元素，从未被直线覆盖的部 分找出最小元素，然后从未画直线的行减去此最小元素，并 从画直线的列加上此最小元素，得出新的系数矩阵，然后，返 回第二步。 4 仿真研究与结果 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 本文实验是在 MATLAB7． 0 环境下完成的，验证本文算 法的实验结果。由表 1 的结果可以看到，车的行驶距离乘上 车每公里的运输成本量一般等于车辆的运输成本。当调度 车型不能满足该成本时，则可以考虑换车辆类型，车辆的运 输成本如表 2 所示。 表 1 调度车辆与请求任务的距离 车辆 1(M)2(L)3(S)4(S)5(L)6(M)7(L)8(M)9(S)10(L) 1(M) 10 20 15 19 30 5 18 16 13 12 2(S) 4 12 8 9 16 20 22 17 9 6 3(L) 3 5 12 9 16 25 6 8 11 8 4(M) 13 21 8 14 9 16 31 6 21 12 5(S) 15 23 24 9 18 5 21 13 9 12 表 2 车辆的运输成本 车辆 1(M)2(L)3(S)4(S)5(L)6(M)7(L)8(M)9(S)10(L) 1(M) 30 80 " " 120 15 72 48 " 48 2(S) 12 48 16 18 64 60 88 51 18 24 3(L) " 20 " " 64 " 24 " " 32 4(M) 39 84 " " 36 48 124 12 " 48 5(S) 45 92 48 10 72 15 64 39 18 48 由于任务请求与可用来调度的车辆数量不同，为了满足 匈牙利解法的条件，算法必须补充 5 个虚构的任务请求，使 得任务请求和调度的车辆数量相等。可以获得效率矩阵 C: 30 80 " " 120 15 72 48 " 48 12 48 16 18 64 60 88 51 18 24 " 20 " " 64 " 24 " " 32 39 84 " " 36 48 124 12 " 48 45 92 48 10 72 15 64 39 18 48 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 首先调整效率矩阵 C，使得每一行和每一列中至少有一 个 0 元素，再从上述矩阵中找出不同行、不同列的 10 个不同 的零元素，具体做法是从 0 元素最少的行中开始，取出 0，做 上标记，然后划出相同列和行的 0 元素。依此类推，直到标 出找出不同行、不同列的 10 个不同的零元素。由此可得该 调度问题的最优解矩阵(xij) : 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0  0 0 0 0 0 0 0 0 0 1 由于后五行为虚构的任务，所以只取前五行的非零项: x16、x21、x32、x48、x54，，于是获得了最优的调度结果，如下:车辆 1去完成要求 2，车辆 2 去完成要求 3，车辆 4 去完成要求 5， 车辆 6 去完成要求求 1，车辆 8 去完成要求 4，所以依据上文 调度算法，最终的调度成本为: —843— F = ∑ m i = 1 ∑ l j = 1 cj* dij* xij = c16 + c21 + c32 + c48 + c54 = 69 采用调度算法得出的结果和表 2 对比发现，本文得出的 调度算法是包含了所有可能出现的情况，在所有调度中可以 说是成本是最低的，然后再根据运输成本最小的原则，从而 得出了最优的调度，满足了请求。本文提出的算法计算量 小，算法复杂度低有效节约了成本。 5 结论 在现实问题中线性规划理论有着广泛的用途，解决了许 多一般运输问题，真正落实到了实处。本文提出了基于线性 规划车辆调度算法，并建立的数学模型，同时采用了匈牙利 算法对模型进行了求解，最后仿真结果表明，本文提出的算 法能够达到最优解，同时能够更好的实现车辆有效调度。具 有一定的推广价值。 参考文献: ［1］ 李军，郭强． 车辆调度问题的改进表上作业法［J］．西南交通大 学报，2000，35(5) :2 － 6． ［2］ 许箐，雷定湭，邓煜阳． 基于区位理论的物流中心车辆调度优 化算法［J］． 现代物流，2007 － 9． ［3］ 郎茂祥，胡思继． 车辆路径问题的禁忌搜索算法研究［J］． 管 理工程学报，2004，18(1) :81 － 84． ［4］ B Kazaz，K Altinkemer． Optimization of multi － feeder (depot) printed circuit board manufacturing with error guarantees［J］． Eu- ropean Journal of Operational Research，150 2003，150:370 － 394． ［5］ 王帅． 煤矿井下基于改进 A* 算法的移动机器人路径规划 ［J］． 煤矿机械，2008，29(11) :65 － 70． ［6］ 李宁，陈彬，徐凯． 一种基于道路网路拓扑改进的格网空间索 引算法［J］． 上海师范大学学报(自然科学版) ，2008，37(5) : 482 － 483． ［7］ 经怀明，张立军． 多车型车辆调度问题的建模与仿真［J］． 计 算机仿真，2007 － 4． ［作者简介］ 宋维堂(1968． 06 －) ，男(汉族) ，安徽颖上人，在职 研究生，应用数学硕士，主要研究方向:计算机应用 方向; 张淑梅(1968． 10 －) ，女(汉族) ，山东莱州人，在职 研究生，计算机应用硕士，主要研究方向:计算机应 用方向  。 (上接第 330 页) 过程进行优化和改进后，所得的谐振网络参数能更有效的提 高变换器的变换效率。 图 10 参数优化前后的效率变换比较曲线 5 结论 论文针对 LLC谐振变换器的基频分量法在提高变换器 转换效率方面的局限性，提出一种基于时域分析的方法，以 变换器的状态方程为基础进行推导分析，理论上保证变换过 程中的参数信息不丢失，从传导损耗和开关损耗两方面提高 变换效率。最后通过实验验证，与采用基频分量法相比，采 用该方法 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 的谐振参数能有效减少变换器损耗，提高转换 效率。 参考文献: ［1］ 马皓，祁丰． 一种改进的 LLC 变换器谐振网络参数设计方法 ［J］． 中国电机工程学报，2008，(28)33:6 － 11． ［2］ 余昌斌． LLC 谐振半桥 DC － DC 变换器的研究［D］． 重庆大 学，2007 － 11． ［3］ 方宇，徐德鸿，张艳军． 高功率密度 LLC 谐振变换器的研究 ［J］． 电力电子技术，2007，(41)8:16 － 18． ［4］ 赵磊． LLC谐振变换器的研究［D］． 西南交通大学，2008 － 6． ［5］ 吴小华，徐刚． 飞机供电系统的 Saber 仿真［J］． 计算机仿真， 2008，25(2) :70 － 73． ［6］ 周伟成，马皓，张海军． 半桥 LLC 谐振变换器效率优化方案的 研究［J］． 电力电子技术，2007，41(9) :57 － 59． ［作者简介］ 于平义(1954 －) ，男(汉族) ，陕西西安人，硕士，西 安理工大学自动化学院高级工程师，主要研究方向 为电力电子技术的研究与应用; 赵敏玲(1969 －) ，女(汉族) ，陕西西安人，硕士，西 安理工大学自动化学院副教授，主要从事电子科学 与技术方面的研究与应用。 —943—