应急物流配送优化的改进最邻近算法研究

应急物流配送优化的改进最邻近算法研究 李坤颖１　杨　扬１　侯凌霞２ （昆明理工大学交通 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 学院１　昆明６５０２２４）　（广州岭南职业技术学院管理学院２　广州５１０６６３） 摘　要　应急物流配送研究的核心是最短路径选择问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 。以最邻近算法为基础，针对以往只能解决 一个配送仓库对应多个救灾中心问题的局限性，提出一种多个配送仓库同时对应多个救灾中心的改 进最邻近优化算法。通过仿真实验证明该算法具有良好的适用性。 关键词　应急物流配送；最邻近算法；配送优化 中图分类号：Ｆ２２４　　文献标志码：Ａ　　ＤＯＩ：１０．３９６３／ｊ．ＩＳＳＮ　１６７４－４８６１．２０１１．０３．０１０ 收稿日期：２０１０－１０－１０　　修回日期：２０１１－０４－２０ 第一作者简介：李坤颖（１９８４），硕士生．研究方向：物流规划与管理．Ｅ－ｍａｉｌ：ｋｋｙｙ２２＠ｖｉｐ．ｑｑ．ｃｏｍ ０　引　言 应急物流，是指为应对严重自然灾害、突发性 公共卫生事件及军事冲突等突发事件而对物资、 人员、资金的需求进行紧急保障的一种特殊物流 活动。通常情况下，事件的发展都比较迅速，而且 带有区域性。为了在最短时间内将物资运送到灾 区及救灾机构并顺利发放到灾民手中，在事件发 生初期，就应该做好充分的准备及物资调配工 作［１］。 目前，求解物资配送最短路径问题，主要有 Ｄｉｊｋｓｔｒａ算法、Ｆｌｏｙｄ算法以及最邻近算法，其主 要问题是单一源点配送。Ｔｏｔｈ和 Ｖｉｇｏ、Ｌａｐｏｒｔｅ 等建立了多种变形的路径优化选择模型，并给出 了相应的算法［２－３］。田晟通过计算２点之间的最 短路线来决定多个配送点之间的最佳配送线路， 即解决的是单源最短路径问题［４］。陈钢铁在时间 窗条件下对应急物资运输路径优化问题进行了研 究［５］。贾立双提出一种单车场多车型调度算法， 解决单个配送中心对其辐射范围内的需求点调配 车型及确定配送路线［６］。但是，对于大规模的应 急物流配送，救灾物资往往来源于不同地域的储 备仓库。本文根据现实情况，设计了一种基于最 邻近理论的改进算法，来满足多来源点多配送点 的问题求解。 １　数学模型 随着时间的推移，救援条件及各受灾点的实 际情况在不断的发生新变化，设置时间参数ｔ，将 总救援时长分为ｎ个阶段，ｔｎ 为第ｎ个救援阶段； 为简化算法，在该模型中不考虑各个集散中心对 物资种类需求的差异性，设置危害程度因素Ｄｉｎ ≤１，Ｄｉｎ越小，表示集散中心ｉ在Ｔｎ 救援阶段对 物资的需求越急迫；在各储备仓库和集散中心之 间有多种运输方式，各节点之间运输方式的效率 以运输时间来表示，２节点间不存在或不能正常 使用时，运输时间设为∞；有多个储备仓库负责物 资的供应，每个储备仓库可以同时给多个集散中 心提供物资，各集散中心的物资只来源于一个储 备仓库，且２点之间只选择一种运输方式。通常 在救援期内，应急物资都存在供不应求的情况，因 此，该模型利用交通规划中的重力模型法进行调 整，将各救灾点集散中心的实际物资配送量按比 例缩减为 ｒｉｎ ＝Ｒｊ （ｎ ∑ｉ∈ＧＧｉｎ／∑ｊ∈ＳＲｊ ）ｎ 　　建模如下： ｆ（ｘ）＝ｍｉｎ∑ ｉ∈Ｈ ∑ ｊ∈Ｈ ∑ ｍ∈Ｖ ｔｉｊｍｎｘｉｊｍｎＤｊｎ 　ｎ ∈Ｎ （１） 　　约束条件： ∑ ｍ∈Ｖ ∑ ｉ∈Ｈ Ｘｉｊｍ ＝１ｎ ∈Ｎ　　　　　　 （２） ∑ ｉ∈Ｈ ∑ ｍ∈Ｖ ＹｉｊｍｔＯｉｊｍｔ ≥ＲｊｔＶｊ∈Ｓ　　　　　　（３） Ｎｉｎ ≤ｒｊｎ ｉ∈Ｇ，ｊ∈Ｓ，ｎ∈Ｎ （４） Ｘｉｊｍｎ ＝０ｏｒ１ｉ，ｊ∈Ｓ，ｍ∈Ｖ，ｎ∈Ｎ （５ 烅 烄 烆 ） 　　模型中决策变量Ｘｉｊｍｎ表示第ｎ救援阶段，从 ０４ 交通信息与安全　２０１１年第３期　第２９卷　总１６１期 点ｉ（ｉ∈Ｈ）到点ｊ（ｊ∈Ｈ）是否选择运输方式ｍ进 行物资运送，选择Ｘｉｊｍｎ＝１，否则Ｘｉｊｍｎ＝０；Ｙｉｊｍｔ为 ｔ时间内，从点ｉ到ｊ（ｉ，ｊ∈Ｈ），运输方式ｍ 的运 送次数，ｔ≤Ｔ；Ｇ为投入使用的Ｒ 处物资储备仓 库；Ｓ表示需要提供应急物资的集散中心；Ｈ 指所 有集散中心和储备仓库的总和；Ｖ 表示各种运输 方式的集合；Ｎｉｎ为物资储备仓库ｉ（ｉ∈Ｇ）在第ｎ 时段内可以供应的物资总量；Ｒｊｎ为集散中心ｊ（ｊ ∈Ｓ）在第ｎ时段内对物资的需求总量；ｒｊｎ为调整 后的集散中心ｊ的ｎ阶段对物资的需求量；ｔｉｊｍｎ为 第ｎ救援阶段，从点ｉ（ｉ∈Ｈ）到点ｊ（ｊ∈Ｈ），运输 方式ｍ所耗时间；Ｑｉｊｍ为从点ｉ（ｉ∈Ｈ）到点ｊ（ｊ∈ Ｈ），运输方式ｍ的一次运输量，不随时间变化。 目标函数式（１）表示所耗时间最短。约束式 （２）表示每一个救灾点集散中心ｊ都会被访问，且 任意２集散中心ｉ、ｊ之间选用消耗时间最短的运 输方式；约束式（３）表示一定时间ｔ内，各种运输 方式运送的物资总和，能满足集散中心ｊ对物资 的需求总量；约束式（４）表示任一物资供应点都可 以单独承担一个物资需求点的物资配送工作；约 束式（５）表示保证目标函数取整。 ２　改进的最邻近算法 ２．１　问题的提出 借鉴文献［７］的编码方法，以０１，０２，０３，…，ｒ 表示储备仓库；１，２，３，…，ｉ表示救灾点集散中 心。网络中最多有ｒ条配送路径，每条配送路径 都始于供应点终于配送点。例如对于３个物资供 应点，９个物资需求点的配送网络而言，抗体 ０２１２３０２０１４５０１０３６７８９０３表示如下车辆配送线路 安排：子路线１：０１—４—２—３—０１；子路线２：０２— １—５—０２；子路线３：０３—６—７—８—９—０３［８］。 其一般求解配送问题的最邻近算法基本原理 过程描述如下：从物流配送中心出发寻找距其最 近的、未访问的网点作为第一个网点并设为已访 问，然后以该点为中心搜索与之相邻的、未访问的 网点，如果加上该点不会超出容量限制，则将该点 加入到线路中并设为已访问，否则结束该条线路； 然后以加入的点作为中心继续搜索，直到找不到 相邻的、未访问的网点为止，结束该条线路。重复 上述步骤，寻找距离物流配送中心的最近的未访 问的网点作为新线路的第一个网点，生成新的线 路，直到将所有的网点都访问过。这样也能得到 问题的解，但从理论上来说不一定是最优解。最 邻近算法的优势在于解决一个供应点对应多个需 求点的问题，它可以得到最优解。但是对于解决 多个供应点对应多个需求点的问题还需要进一步 改进最邻近算法才能实现。 ２．２　算法的改进 依据最邻近算法的原理和模型的内容，将最 邻近点的搜索以时间作为衡量 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 ，搜索到中心 消耗时间最短的节点，容量限制以子路线上的物 资需求总量不超过提供物资的供应点的最大供应 量为准。改进之后的模型计算步骤可以实施如 下。 步骤１。将各集散中心所辖区域的受灾情况 进行分类，确定灾情严重程度因素值Ｄｉｎ，０≤Ｄｉｎ ≤１。 步骤２。确定ｔｉｊｍｎ矩阵，因任意节点ｉ和ｊ之 间只选用一种运输方式，所以可将矩阵ｔｉｊｍｎ转化 成ｔｉｊｎ。 步骤３。利用公式计算ｒｊｎ值。 步骤４。将矩阵带入ｔｉｊｎ×Ｄｉｎ进行下列计算。 １）选择矩阵中最小值ｔｉｊｎ×Ｄｉｎ（ｉ∈Ｇ，ｊ∈Ｓ）， 将ｉ作为第一个物资供应点，ｊ作为第一个物资被 配送点， 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 ｉｊ，并将点ｉ、ｊ作为已访问。 ２）再以物资需求点ｊ作为起点，从未访问的 矩阵中选择最小值ｔｊｋｎ×Ｄｋｎ（ｊ，ｋ∈Ｓ），如果ｒｊｎ＋ ｒｋｎ≥Ｎｉｎ，子线路结束，并求出剩余值Ｎｉｎ－ｒｊｎ，否 则记录ｉｊｋ，设ｋ为已访问，继续搜索下一个节点。 ３）一条子线路结束后，在剩下的未访问的矩 阵中继续重复步骤１，找到新的物资供应点ｉ，将 Ｎｉｎ－ｒｊｎ值加在新供应点的物资供应量上，继续步 骤２。 ４）直到所有节点全被访问，计算结束。 ３　实例计算 设Ｔｎ＝Ｔ１ 时，３个物资供应点０１、０２、０３向 １２个物资需求点配送物资，见图１。各个物资供 应点的供应量以及各物资需求点的需求量见下表 （表中需求量和供应量均为模糊数值，无量纲）。 图１　应急物资供应点和需求点 Ｆｉｇ．１　Ｅｍｅｒｇｅｎｃｙ　ｓｕｐｐｌｉｅｓ　ｓｕｐｐｌｙ　ａｎｄ　ｄｅｍａｎｄ 运用改进最邻近算法对上述问题进行求解。 １４应急物流配送优化的改进最邻近算法研究———李坤颖　杨　扬　侯凌霞 以 Ｍａｔｌａｂ７．０为工具，编写计算程序。先求出调 整后的各救灾点集散中心的物资需求量ｒｊｎ，如表 ５所示。 表１　各供应点的最大供应量 Ｔａｂ．１　Ｔｈｅ　ｍａｘｉｍｕｍ　ｓｕｐｐｌｙ　ｏｆ　ｓｕｐｐｌｙ　ｐｏｉｎｔｓ 供应点Ｐｉ ０１　 ０２　 ０３ 供应量Ｎｉｎ １０　 ２０　 １５ 表２　各需求点的需求量以及受灾因素值 Ｔａｂ．２　Ｄｅｍａｎｄ　ａｎｄ　Ｆａｃｔｏｒｓ　ａｆｆｅｃｔｅｄ 需求点Ｒｊ Ｐ１ Ｐ２ Ｐ３ Ｐ４ Ｐ５ Ｐ６ Ｐ７ Ｐ８ Ｐ９ Ｐ１０Ｐ１１Ｐ１２ 需求量Ｒｊｎ ８　 ６　 ８　 １０　１２　１０　６　 ４　１０　６　 ２　 ８ Ｄｊ ０．３　０．５　０．７　０．４　０．１　０．３　０．５　０．６　０．６　０．７　０．８　０．３ 表３　各供应点到需求点的消耗时间 Ｔａｂ．３　Ｓｕｐｐｌｙ　ｐｏｉｎｔｓ　ｔｉｍｅ　ｔｏ　ｄｅｍａｎｄ　ｐｏｉｎｔｓ 供应点 Ｐ１ Ｐ２ Ｐ３ Ｐ４ Ｐ５ Ｐ６ Ｐ７ Ｐ８ Ｐ９ Ｐ１０ Ｐ１１ Ｐ１２ ０１　 ９　 １４　２１　２３　２２　２５　３２　３６　３８　４２　５０　５２ ０２　 ４４　５８　５７　４９　３７　 ７　 １１　１４　２０　２４　２７　３０ ０３　 ５２　５５　４３　４９　６０　６３　２７　３７　３５　６３　３４　２８ 表４　１２个物资需求点之间的耗时 Ｔａｂ．４　Ｂｅｔｗｅｅｎ　ｔｈｅ　ｔｉｍｅ－ｃｏｎｓｕｍｉｎｇ　ａｎｄ　ｄｅｍａｎｄ　ｐｏｉｎｔｓ ＪＤ　Ｐ１ Ｐ２ Ｐ３ Ｐ４ Ｐ５ Ｐ６ Ｐ７ Ｐ８ Ｐ９ Ｐ１０ Ｐ１１ Ｐ１２ Ｐ１ ０　 ５　 １２　２２　２１　２４　３１　３５　３７　４１　４９　５１ Ｐ２ ５　 ０　 ７　 １７　１６　２３　２６　３０　３６　３６　４４　４６ Ｐ３ １２　 ７　 ０　 １０　２１　３０　２７　３７　４３　３１　３７　３９ Ｐ４ ２２　１７　１０　 ０　 １９　２８　２５　３５　４１　２９　３１　２９ Ｐ５ ２１　１６　２１　１９　 ０　 ９　 １０　１６　２２　２０　２８　３０ Ｐ６ ２４　２３　３０　２８　 ９　 ０　 ７　 １１　１３　１７　２６　２７ Ｐ７ ３１　２６　２７　２５　１０　 ７　 ０　 １０　１６　１０　１８　２０ Ｐ８ ３５　３０　３７　３５　１６　１１　１０　 ０　 ６　 ６　 １４　１６ Ｐ９ ３７　３６　４３　４１　２２　１３　１６　 ６　 ０　 １２　１２　２０ Ｐ１０ ４１　３６　３１　２９　２０　１７　１０　 ６　 １２　 ０　 ８　 １０ Ｐ１１ ４９　４４　３７　３１　２８　２６　１８　１４　１２　 ８　 ０　 １０ Ｐ１２ ５１　４６　３９　２９　３０　２７　２０　１６　２０　１０　１０　 ０ 表５　调整后的需求量ｒｊｎ Ｔａｂ．５　Ａｄｊｕｓｔｅｄ　ｄｅｍａｎｄ 需求点Ｒｊ Ｐ１ Ｐ２ Ｐ３ Ｐ４ Ｐ５ Ｐ６ Ｐ７ Ｐ８ Ｐ９ Ｐ１０Ｐ１１Ｐ１２ 需求量ｒｊｎ ４　 ３　 ４　 ５　 ６　 ５　 ３　 ２　 ５　 ３　 １　 ４ 　　最后运用软件运算得到结果： 路线一：０２—Ｐ６—Ｐ５—Ｐ７—Ｐ８ 表示首先由 供应量为２０的０２供应点向需求量为５的Ｐ６ 点 运送物资，其次向需求量为６的Ｐ５ 点运送物资， 再向需求量为３的Ｐ７ 点运送物资，最后向需求 量为２的 Ｐ８ 点运送物资。同理路线二：０１— Ｐ１—Ｐ２—Ｐ３；路线三：０３—Ｐ１２—Ｐ１０—Ｐ１１—Ｐ９— Ｐ４（如图２所示）。 图２　应急物流的配送路线及配送量 Ｆｉｇ．２　Ｄｉｓｔｒｉｂｕｔｉｏｎ　ｌｉｎｅ　ａｎｄ　ｑｕａｎｔｉｔｙ ４　结束语 介绍了在应急事件下，救援物资的配送问题， 从各地储备仓库到事件发生地区的长距离运输， 这一过程涉及了公路、铁路、水运和航空４种运输 方式，各种运输方式消耗的时间截然不同，必须选 取适合的运输方式完成两点之间的运输。此外， 由于各物资配送中心管辖的受灾地区的受灾程度 的差异性，设置了参数Ｄ 来表示各受灾点的生 命、财产等受害程度，并对灾情比较严重的地区进 行优先配送。通过对最邻近算法的改进，解决了 多个储备仓库对应多个救灾集散中心的物资配送 问题，通过实例证明该算法具有很好的适应性。 参考文献 ［１］　侯凌霞．突发事件下应急物流中心物资配送优化研 究［Ｄ］．昆明：昆明理工大学，２０１０． ［２］　Ｒｅｅｓ　Ｗ　Ｅ，Ｗａｃｋｅｒｎａｇｅ　ｌ　Ｍ．Ｏｕｒ　ｅｃｏｌｏｇｉｃａｌ　ｆｏｏｔ－ ｐｒｉｎｔ：Ｒｅｄｕｃｉｎｇ　ｈｕｍａｎ　ｉｍｐａｃｔ　ｏｎ　ｔｈｅ　ｅａｒｔｈ［Ｍ］． Ｇａｂｒｉｅｌａ　Ｉｓｌａｎｄ，Ｂｒｉｔｉｓｈ　Ｃｏｌｏｍｂｉａ：Ｎｅｗ　Ｓｏｃｉｅｔｙ Ｐｕｂｌｉｓｈｅｒｓ，１９９６． ［３］　Ｓｔｅｆａｎ　Ｇｏｓｓｌｉｎｇ．Ｅｃｏｌｏｇｉｃａｌ　ｆｏｏｔｐｒｉｎｔ　ａｎａｌｙｓｉｓ　ａｓ　ａ ｔｏｏｌ　ｔｏ　ａｓｓｅｓｓ　ｔｏｕｒｉｓｍ　ｓｕｓｔａｉｎａｂｉｌｉｔｙ［Ｊ］．Ｅｃｏｌｏｇｉｃａｌ Ｅｃｏｎｏｍｉｃｓ，２００２（４３）：１９９－２１１． ［４］　田　晟．基于Ｄｉｊｋｓｔｒａ算法的物流配送系统最短路 径程序设计［Ｊ］．交通标准化，２００９（１３）：８９－９２． ［５］　陈钢铁，帅斌．在时间窗条件下应急物资运输路径 优化问题研究［Ｊ］．铁道运输与经济，２０１０，３２（３）： ７０－７２． ［６］　贾立双，李　静．基于一种改进算法的单车场多车 型车辆调度研究［Ｊ］．中国制造业信息化，２００８，３７ （１０）：８－１１． ［７］　郑日荣，毛宗源，罗欣贤．基于耿氏距离和精英交叉的 免疫算法研究［Ｊ］．控制与决策，２００５，２０（２）：１６１－１６４． ［８］　潘立军，董雄报．改进免疫克隆选择算法在 ＶＲＰ中 的应用［Ｊ］．桂林电子科技大学学报，２００６，２６（６）： ４７３－４７６． （下转第４６页） ２４ 交通信息与安全　２０１１年第３期　第２９卷　总１６１期 表１　由波形图提取的车辆信息 Ｔａｂ．１　Ｔｈｅ　ｍｅｓｓａｇｅ　ｏｆ　ｔｈｅ　ｖｅｈｉｃｌｅ　ｆｒｏｍ　ｔｈｅｓｅ　ｗａｖｅｓ 车辆经过时间 （２０１０－０６－２３） 波长覆盖 时间序列 点数 峰值覆盖 时间序列 点数 车长 ／ｍ 车速／ （ｋｍ·ｈ－１） 车型 １６：３７：１８　 ４　５１８　 ７４　 ６．９２　 １１．０２　 ３ １７：０５：１９　 ３　２６１　 １１２　 ３．３　 ７．２８　 ２ １７：１４：３９　 ３　９８８　 ７２　 ６．２７　 １１．０３　 １ １７：３６：２０　 ５　５０４　 ６１　 １０．２２　 １３．７７　 ３ １７：４９：３９　 ３　００２　 ９７　 ３．５１　 ８．４１　 ２ 测传感器数据的是否达到平稳状态而非传统的单 纯的采用基值来判定波形记录是否结束，并且提 出的一种加权动态基值的调整 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，使得阈值具 有一定稳定性的同时，还具有一定的动态特性。 并给出实时在线的算法验证，实验证明了该算法 具有较高的准确率。但是在算法的改进上，仍然 还是可以增加一些智能算法来更好的进行波形提 取和车辆信息的提取，以提高算法的效率，这也 为今后作进一步的研究指明了方向。 参考文献 ［１］　Ｃｏｉｆｉｍａｎ　Ｂ，Ｄｈｏｏｒｊａｔｙ，Ｌｅｅ　Ｚｕ－Ｈｓｕ．Ｅｓｔｉｍａｔｉｎｇ　ｍｅｄｉ－ ａｎ　ｖｅｌｏｃｉｔｙ　ｉｎｓｔｅａｄ　ｏｆ　ｍｅａｎ　ｖｅｌｏｃｉｔｙ　ａｔ　ｓｉｎｇｌｅ　ｌｏｏｐ　ｄｅｔｅｃ－ ｔｏｒｓ［Ｊ］．Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　Ｐａｒｔ　Ｃ，２００３，１１（３－ ４）：２１１－２２０． ［２］　Ｂｄｕｌｈａｉ　Ｂ　Ａ，Ｔａｂｉｏ　Ｓ　Ｍ．Ｓｐｏｔｉｏｔｅｍｐｏｒａｌ　ｉｎｄｕｃｔａｎｃｅ ｐａｔｔｅｍ　ｒｅｃｏｇｎｉｔｉｏｎ　ｆｏｒ　ｖｅｈｉｃｌｅ　ｒｅ－ｄｅｎｔｉｆｉｃａｔｉｏｎ［Ｊ］． Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　Ｐａｒｔ　Ｃ，２００３，１１（３－４）：２２３－ ２３９． ［３］　任明武，杨万扣．一种视频液位检测中液位的定位 算法［Ｊ］．计算机工程与应用，２００７，４３（２２）：２０４－ ２０６． ［４］　谷口庆治．数字图像处理：基础篇［Ｍ］．朱　虹，廖　 成，乐　静，等译．北京：科学出版社，２００２． ［５］　宋　丹，徐蔚鸿．基于模糊理论的车型识别［Ｊ］．计算 机技术与发展，２００６（３）：４７－４９． ［６］　樊海泉，董德存．基于模式匹配算法的车型识别研 究［Ｊ］．微型电脑应用，２００２，１８（４）：２０－２２． ［７］　耿彦峰，马　钺．基于模糊模式识别的车型分类研 究［Ｊ］．计算机工程，２００２，２８（１）：１３３－１３５． ［８］　潘且鲁，张颖川，潘俊民．基于图像处理技术的液位 测控系统［Ｊ］．自动化仪表，２０００（４）：３６－３８． Ｖｅｈｉｃｌｅ　Ｄｅｔｅｃｔｉｏｎ　Ｍｅｔｈｏｄ　Ｂａｓｅｄ　ｏｎ　Ｍａｇｎｅｔｏ　Ｒｅｓｉｓｔｉｖｅ　Ｓｅｎｓｏｒｓ ＲＯＮＧ　Ｍｅｉ　１　ＨＵＡＮＧ　Ｈｕｉｘｉａｎ２　ＸＵ　Ｊｉａｎｍｉｎ３ （Ｃｏｌｌｅｇｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉａｎｇｔａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉａｎｇｔａｎ４１１１０５，Ｈｕｎａｎ，Ｃｈｉｎａ）１ （Ｓｃｈｏｏｌ　ｏｆ　Ｃｉｖｉｌ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｔｒａｎｓｐｏｒｔａｔｉｏｎ， Ｓｏｕｔｈ　Ｃｈｉｎａ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｇｕａｎｇｚｈｏｕ５１０６４１，Ｃｈｉｎａ）２ Ａｂｓｔｒａｃｔ：Ｍａｇｎｅｔｏｍｅｔｅｒ　ｄｅｔｅｃｔｏｒ　ｉｓ　ａ　ｋｉｎｄ　ｏｆ　ｄｅｔｅｃｔｉｏｎ　ｅｑｕｉｐｍｅｎｔ　ｗｈｉｃｈ　ｃａｎ　ｄｙｎａｍｉｃａｌｌｙ　ｄｅｔｅｃｔ　ｔｈｅ　ｃｈａｎｇｅｓ　ｏｆ　ｍａｇ－ ｎｅｔｉｃ　ｆｉｅｌｄ．Ａ　ｍｅｔｈｏｄ　ｏｆ　ｖｅｈｉｃｌｅ　ｄｅｔｅｃｔｉｏｎ　ｗａｓ　ｐｒｏｐｏｓｅｄ　ｂａｓｅｄ　ｏｎ　ｔｈｉｓ　ｍａｇｎｅｔｏｍｅｔｅｒ　ｄｅｔｅｃｔｏｒ．Ｔｈｅ　ｐｒｅｐｒｏｃｅｓｓｉｎｇ　ａｎｄ　ｔｈｅ ｓｔｅｐｓ　ｏｆ　ｆｅａｔｕｒｅ　ｏｆ　ｔｈｅ　ｗａｖｅｆｏｒｍ　ｅｘｔｒａｃｔｉｏｎ　ｏｆ　ｔｈｅ　ｃｏｌｌｅｃｔｉｏｎ　ｄａｔａ　ｗｅｒｅ　ｉｎｔｒｏｄｕｃｅｄ．Ｔｈｅ　ｍｅｔｈｏｄ　ｔｏ　ｄｅｔｅｃｔ　ｔｈｅ　ｓｐｅｅｄ　ａｎｄ　ｔｈｅ ｔｙｐｅ　ｏｆ　ｔｈｅ　ｖｅｈｉｃｌｅ　ｅｆｆｅｃｔｕａｌｌｙ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｄｙｎａｍｉｃ　ｔｈｒｅｓｈｏｌｄ　ｖａｌｕｅ　ｗａｓ　ｄｉｓｃｕｓｓｅｄ　ｔｈｒｏｕｇｈ　ｕｓｉｎｇ　２Ｍａｇｎｅｔｏ　ｒｅｓｉｓｔｉｖｅ　ｓｅｎ－ ｓｏｒｓ　ｗｈｉｃｈ　ｗｅｒｅ　ｆｉｔｔｅｄ　ｉｎ　ｔｈｅ　ｒｏａｄ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ａｃｃｕｒａｃｙ　ｏｆ　ｔｈｅ　ｖｅｈｉｃｌｅ　ｄｅｔｅｃｔｉｏｎ　ｍｅｔｈｏｄ　ｂａｓｅｄ ｏｎ　ｍａｇｎｅｔｏ　ｒｅｓｉｓｔｉｖｅ　ｓｅｎｓｏｒｓ　ｃａｎ　ｂｅ　ａｓ　ｈｉｇｈ　ａｓ　９８％． Ｋｅｙ　ｗｏｒｄｓ：ｖｅｈｉｃｌｅ　ｄｅｔｅｃｔｏｒ；ｗａｖｅｆｏｒｍ　ｆｅａｔｕｒｅｓ；ｍａｇｎｅｔｏ　ｅｆｆｅｃｔ；ｉｎｔｅｌｌｉｇｅｎｔ　ｔｒａｎｓｐｏｒｔ　ｓｙ 檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾檾 ｓｔｅｍ （上接４２页） Ｉｍｐｒｏｖｅｄ　Ｎｅａｒｅｓｔ　Ｎｅｉｇｈｂｏｒ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｅｍｅｒｇｅｎｃｙ　Ｓｕｐｐｌｉｅｓ　Ｄｉｓｔｒｉｂｕｔｉｏｎ ＬＩ　Ｋｕｎｙｉｎｇ１　ＹＡＮＧ　Ｙａｎｇ１　ＨＯＵ　Ｌｉｎｇｘｉａ２ （Ｆａｃｕｌｔｙ　ｏｆ　Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｋｕｎｍｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｋｕｎｍｉｎｇ６５０２２４，Ｃｈｉｎａ）１ （Ｆａｃｕｌｔｙ　ｏｆ　Ｍａｎａｇｅｍｅｎｔ，Ｌｉｎｇｎａｎ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｇｕａｎｇｚｈｏｕ５１０６６３，Ｃｈｉｎａ）２ Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｃｏｒｅ　ｏｆ　ｅｍｅｒｇｅｎｃｙ　ｌｏｇｉｓｔｉｃｓ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｒｅｓｅａｒｃｈ　ｉｓ　ｔｈｅ　ｓｈｏｒｔｅｓｔ　ｐａｔｈ　ｓｅｌｅｃｔｉｏｎ　ｐｒｏｂｌｅｍ．Ｂａｓｅｄ　ｏｎ　ｔｈｅ ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒ　ａｌｇｏｒｉｔｈｍ，ａｎ　ｉｍｐｒｏｖｅｄ　ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｍａｎｙ－ｔｏ－ｍａｎｙ　ｗａｓ　ｐｒｅｓｅｎｔｅｄ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｐｒｏｂｌｅｍ ｏｆ　ｏｎｅ－ｔｏ－ｍａｎｙ　ｉｎ　ｔｈｅ　ｐａｓｔ．Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｈａｓ　ｇｏｏｄ　ａｄａｐｔａｂｉｌｉｔｙ． Ｋｅｙ　ｗｏｒｄｓ：ｅｍｅｒｇｅｎｃｙ　ｌｏｇｉｓｔｉｃｓ　ｄｉｓｔｒｉｂｕｔｉｏｎ；ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒ　ａｌｇｏｒｉｔｈｍ；ｄｉｓｔｒｉｂｕｔｉｏｎ　ｏｐｔｉｍｉｚａｔｉｏｎ ６４ 交通信息与安全　２０１１年第３期　第２９卷　总１６１期