透明配送车辆优化调度算法

透明配送车辆优化调度算法 3 邵贵平 　范荣真 　王其良 〔摘 　要〕　根据国内的道路交通状况和配送需求 , 我们提出了透明配送以减少客户等待的时间 , 并采用节约启发式算法优化配送线路 , 从而有利于提高客户的满意度和物流运输的效益。 〔关键词〕　透明配送 　节约启发式算法 　VSP 　3 　浙江省高校青年教师资助计划项目。 　　现代物流的主要目标是提高客户服务水平和企业的 经济效益 , 而商品的合理配送是提高客户服务满意度和 物流运输效益的关键环节。本文根据我国目前的交通运 输状况和配送需求 , 提出了透明配送。透明配送是指客 户可以在商品送达之前就知道具体的配送时间段 , 从而 大大减少了客户等待的时间 , 同时运用节约启发式算法 优化配送路线。 1. 客户需求 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 客户到超市或商场购物 , 如果采购的是大件商品 , 一般情况下都会要求送货上门。然后超市或商场根据客 户确定的送货日期由配送中心统一配送。其中送货日期 的确定 , 通常有以下两种情况 : 1) 仅指定在某一天送货 , 但未指定在哪个时间段。 2) 不仅指定在某一天送货 , 而且指定在哪个时间 段。 在第一种情况下 , 因为不知道具体的配送时间 , 客 户等待的时间会很长 , 所以常常受到客户抱怨。在这种 情况下 , 配送对客户来说是不透明的。 在第二种情况下 , 客户可以自由安排送货时间 , 但 对配送中心的车辆调度要求会很高 , 甚至导致配送成本 大幅上升。这实际上是一个有时间窗的 VSP (Vehicle Scheduling Problem) 问题。在这种情况下 , 配送对客户来 说是透明的 , 但配送成本会很高 , 所以在目前 , 我国超 市或商场采用第二种配送时间安排的并不多。 2. 透明配送 现在我国超市或商场一般采用第一种配送时间安排 , 客户可以预约在某一天配送 , 但无法知道具体的配送时 间段 , 这对客户来说非常不方便。根据这种情况 , 我们 对配送时间的安排进行调整 , 采用透明配送方式 : 即由 客户指定在某一天送货 , 然后配送中心根据优化的车辆 线路安排确定具体的配送时间段 , 并预先通知客户。这 样客户只需在预定的时间段内准备接收货物就可以了 , 从而大大减少了客户等待的时间 , 提高了客户的满意度。 这样我们就将物流配送车辆优化调度问题变成了透 明配送车辆优化调度问题 , 其求解步骤如下 : 第一步 : 对于没有时间窗的 VSP 问题采用 C - W 节 约启发式算法进行求解 , 获得优化的车辆运行线路。 第二步 : 计算线路上到达每个配送点的预定到达时 间 , 并根据道路交通状况 , 确定到达的时间范围 , 然后 通知客户在该时间范围内准备接收货物。 透明配送车辆优化调度问题具体描述如下 : 一个配送中心 , 拥有容量为 Q 的车辆 , 现在需要为 n 个配送点 P1 , P2 , P3 , ⋯, Pn , 配送商品。已知配送点 i 的货运量为 qi (i = 1 , 2 , ⋯, n) 。求满足货运要求的费 用最小的车辆运行线路 , 并计算到达每个配送点的预定 时间。 一般认为 , 派出一辆车的固定费用远远高于车辆行 驶费用 , 所以我们把求解的目标确定为在极小化车辆的 前提下 , 再极小化运输费用。下面我们来确定透明配送 车辆优化调度问题的数学模型。 为了方便构造数学模型 , 将配送中心的编号定为 0 , 配送点的编号为 1 , 2 , ⋯, n。配送中心和配送配送点 均以点 i (i = 0 , 1 , 2 , ⋯, n) 来表示。定义变量如下 : yki = 　1 　 (配送点 i 的配送任务由车辆 k 完成) 　0 　 (其它) xijk = 　1 　 (车辆 k 从配送点 i 行驶到配送点 j) 　0 　 (其它) si 表示到达配送点 i 的时间。由始发时间 (ST) 、行 驶时间 (t) 、卸货时间 (ut) 构成。 tij表示从配送点 i 到配送点 j 的行驶时间。 uti 表示在配送点 i 进行装卸作业的时间。 则可得车辆优化调度数学模型如下 : minZ = ∑ i ∑ j ∑ k cij xijk si = si - 1 + t (i - 1 ,i) + uti - 1 　i = 1 , 2 , ⋯, n ; ∑ i giyki ≤Q 　Π k ∑ k yki = 1 i = 0 , 1 , 2 , ⋯, n ∑ i xijk = ykj j = 0 , 1 , 2 , ⋯, n ; Π k ∑ j xijk = yki i = 0 , 1 , 2 , ⋯, n ; Π k —611— 第 24 卷 　第 8 期 2005 年 8 月 工业技术经济 Vol124 , No18 总第 144 期 X = (xijk) ∈S xijk = 0 或 1 i , j = 0 , 1 , 2 , ⋯, n ; Π k yki = 0 或 1 i , j = 0 , 1 , 2 , ⋯, n ; Π k s0 = ST 其中 S为支路消去约束。 3. 算法描述 输入 : 各配送点货物配送要求和配送点距离矩阵 输出 : 优化的车辆调度安排和各配送点的配送时间 段 原理 : 采用 C - W节约启发式算法进行求解。 具体步骤如下 : 步骤 1 : 计算除配送中心外的所有配送点之间的费 用节约值。s (i ,j) = ci0 + c0j - cij 　i , j = 1 , 2 , ⋯, n ; cij 表示车辆从配送点 i 行驶到配送点 j 的费用 , 可以用配送 点 i 行驶到配送点 j 的距离来表示。 令 M = {s (i , j) | s (i , j) > 0} 步骤 2 : 在 M内按 s (i , j) 从大到小的顺序排列。 步骤 3 : 若 M =Φ , 则终止。否则对第一项 s (i , j) 进行考察 , 若对应的 (i , j) 满足下述条件之一 : (1) 配送点 i 和配送点 j 均不在已构建的线路上 ; (2) 配送点 i 或配送点 j 在已构建的线路上。但不是 线路的内点 (即不与配送中心相连) ; (3) 配送点 i 和配送点 j 在已构建的不同线路上 , 且 一个是起点 , 一个终点。则转下一步 , 否则转步骤 6。 步骤 4 : 考察配送点 i 和配送点 j 连接后的线路上总 货运量 q , 若 q ≤Q , 则转下一步 , 否则转步骤 6。 步骤 5 : 连接配送点 i 和配送点 j。 步骤 6 : 令 M: = M - s (i , j) , 然后转步骤 3。 步骤 7 : 计算线路上到达每个配送点的预定到达时 间 si , si = si - 1 + t (i - 1 ,i) + uti - 1 　i = 1 , 2 , ⋯, n ; 其中 tij 表示从配送点 i 到配送点 j 的行驶时间 , uti 表示在配送 点 i 进行装卸作业的时间。 步骤 8 : 计算线路上到达每个配送点的配送时间段。 首先根据道路交通状况 , 确定配送时间误差正负Φ , 则 第 i 个配送点的配送时间段为 [ si - Φ , si +Φ]。如果 si - Φ< ST , 则配送时间段取 [ ST , si +Φ]。 采用节约启发式算法主要因为它简单、易于理解、 灵活性好 , 以及在可行性及交互特性方面都较好 , 而且 易于编程 , 运行速度快 , 可以用于 BS结构的网络应用程 序的开发。 4. 算法应用 下面以 10 个配送点的货物配送为例 , 配送点编号为 1 , 2 , ⋯, 10 ; 配送中心的编号为 0。每个配送点的配送 货物的量为 gi , 装卸时间为 uti 。各配送点货物配送要求 见表 1 , 各配送点之间的距离矩阵见表 2。 表 1 　各配送点货物配送要求 配送点 1 2 3 4 5 6 7 8 9 10 gi (吨) 2 215 115 3 115 3 215 3 1 215 uti (小时) 014 015 013 016 013 016 015 016 012 015 表 2 　各配送点之间的距离矩阵 (单位为公里) 配送点 0 1 2 3 4 5 6 7 8 9 10 0 0 11 31 26 21 11 48 29 28 39 21 1 11 0 21 17 18 16 44 25 33 49 32 2 31 21 0 22 33 37 53 39 54 70 51 3 26 17 22 0 14 26 31 17 37 60 47 4 21 18 33 14 0 15 26 8 23 47 38 5 11 16 37 26 15 0 40 24 3 29 34 6 48 44 53 31 26 40 0 19 37 64 62 7 29 25 39 17 8 24 19 0 24 50 44 8 28 33 54 37 23 3 37 24 0 27 30 9 39 49 70 60 47 29 64 50 27 0 23 10 21 32 51 47 38 34 62 44 30 23 0 　　我们假设车辆的行驶时间与距离成正比 , 每辆车的 平均行驶速度为 50 公里/ 小时。则从配送点 i 到配送点 j 的行驶时间为 tij = dij/ 50。 车辆的吨位 　Q = 8 吨 始发时间 　　ST = 6 点 (下转第 133 页) —711— 第 24 卷 　第 8 期 2005 年 8 月 工业技术经济 Vol124 , No18 总第 144 期 EEPROM AT24C256 (用于存放网页) , 成功地实现了一个 功能最小化的微嵌入式 Web 服务器。系统的固件由 Keil C编写 , 上位机的网页烧写程序用 VC开发工具实现。功 能最小化的微 EWS应用背景不同于通用 Web 服务器 , 不 能使用通用 Web 服务器的三个测评指标评测其性能 , 而 应以能否达到应用需求为 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 。实现的 EWS系统在客户 端无需任何专用软件 , 使用微软的 IE 即可浏览所需页 面 , 且可以通过 Web 页面给服务器端发送自定义的控制 信息 , 实现 Web 方式对服务器端远程设备的管理控制。 其主要性能缺陷表现在对页面请求的响应速度不够快 , 原因在于存放页面的存储器是基于速度较慢的串行接口 方式。进一步的工作可以使用其它接口形式的存储器以 提高服务器的响应速度 , 使其可以满足一些工业远程控 制的应用要求。 EWS技术在工业生产中的现场监测和控制设备中的 实际应用逐步深入并不断扩展 , 通过 Web 浏览器获取 EWS中的系统实时信息 , 进而可以实现远程系统的实时 控制、调节和维护。Web 服务器与设备集成在一起 , 用 户通过 Web 浏览器既可监测设备状态 , 同时通过浏览器 编程的方式能够控制设备端的数据采集方式。通过合理 分配计算任务 , 可以充分发挥客户机的强大计算能力 , 减轻设备端的计算负荷。 4 　结束语 本文分析和介绍了基于低速处理器的微嵌入式 Web 服务器技术的主要问题及解决办法。低速处理器在传统 嵌入式系统中大量存在 , 技术较为成熟 , 十分符合嵌入 式系统成本最小化的要求 , 而且服务器自身成本较低 , 客户端无须开发专用软件 , 可以利用现成的 Internet 进行 信息传输 , 大大降低了应用系统的构建成本。基于微嵌 入式 Web 服务器技术建立的新型监测和控制系统 , 必将 有效降低系统运行维护费用 , 提高系统管理水平 , 应用 领域非常广泛 , 市场前景十分广阔。 参 　考 　文 　献 1. 李恒超 , 张家树. 基于嵌入式 Web 的远程监控 研究. 西南交通大学学报 , 2003 , 38 (3) : 2632266 2. NS Manju Nath. Low2cost Techniques Bring Internet Connectivity to Embedded Devices. END , 1999 , 11 ( 11) : 1592166 3. 胡宾鑫 , 方方. 一种嵌入式以太网接口的设计与 实现. 汕头大学学报 , 2003 , 18 (2) : 52～56 4. 康静秋 , 李明 , 贾智平 . 嵌入式互联网络接口的 设计与开发. 工业控制计算机 , 2003 , 19 (1) : 228～230 5. 欧辉灿 , 李小明 . Web 服务器性能评测. 计算机 研究与发展 , 2002 , 39 (5) 作者简介 　曾燕 , 长春工程学院能源动力学院博士研究 生。研究方向 : 工程机器人。赵丁选 , 吉林大学机械科 学与工程学院。冯富秋 , 长春工程学院水利与环境工程 学院。 (上接第 117 页) 程序仿真的结果如下 : 1) 优化的车辆运行线路为 : 线路 1 : 0 - 3 - 6 - 7 - 0 　　　运输量 : 7 线路 2 : 0 - 5 - 8 - 9 - 10 - 0 运输量 : 8 线路 3 : 0 - 1 - 2 - 4 - 0 运输量 : 715 2) 配送时间安排 : 配送点 0 1 2 3 4 5 6 7 8 9 10 到达时间 6∶00 6∶13 7∶02 6∶31 8∶11 6∶13 7∶26 8∶25 6∶34 7∶43 8∶22 　　3) 确定到达每个配送点的的配送时间段。例如我们 将配送时间误差确定为正负 15 分钟 , 则到达每个配送点 的时间段为 : 配送点 0 1 2 3 4 5 6 7 8 9 10 配送时间段 6∶00 [6∶00 , 6∶28 ] [6∶47 , 7∶17 ] [6∶16 , 6∶46 ] [7∶56 , 8∶26 ] [6∶00 , 6∶28 ] [7∶11 , 7∶41 ] [8∶10 , 8∶40 ] [6∶19 , 6∶49 ] [7∶28 , 7∶58 ] [8∶07 , 8∶37 ] 5. 结 　论 本文根据我国道路交通的实际情况和配送需求 , 提 出了透明配送 , 这可以在大大减少客户等待的时间 , 从 而提高客户服务水平 , 促进物流运输效益的优化。 参 　考 　文 　献 1. 李军等 . 物流配送 (第 2 版) . 中国物流出版社 , 2001 2. 骆温平 . 物流与供应链管理. 电子工业出版社 , 2002 3. 有时间窗的集货送货一体化车辆路径规划启发式 算法研究. 物流技术 , 2004 , (5) : 64～66 4. J . J . HOPFIELD and D. W. Tank , Neural compu2 tation of decision in optimization problems Biol. Cybern. , No. 52 , pp. 141 - 152 , 1985 5. Ma Liang , CuiXueli & Yao Jian , Finding the Minimum Ratio Traveling Salesman Tour by Artificial Ants , Systems Engi2 neering and Electronics , Vol114 , No13 , 2003 , pp124～27 作者简介 　邵贵平 , 浙江商业职业技术学院讲师 , 硕士。 研究方向 : 电子商务。范荣真 , 浙江商业职业技术学院 讲师 , 硕士。研究方向 : 网络技术专业。王其良 , 浙江 商业职业技术学院副教授 , 博士。研究方向 : 计算机技 术应用。 —331— 第 24 卷 　第 8 期 2005 年 8 月 工业技术经济 Vol124 , No18 总第 144 期