，支通运输 Ii程 j信息学报 筇 I I奄 第2则 201 3印6月 Journal orTransponati0n Engineering and Information No．2 Vo1．I l Jun．20I 3
基于货物 时间价值 的
物流 网络最优配送路径模型研究
陈文 强 顾 玉磊
长安 大 学 ，经济 管理 学 院 ，西 安 710064
摘 要 ：本文 构建 了物流 配送 网络 中货物 时间价值相 关的最小配送 费用路 径模型 ，并研 究 了其算 法。模 型把整
个配送过程分为运输过程和装卸过程，并且考虑 了由于运输过程和装卸过程时间延迟造成的货物价值损失，这
也 是和其 它类似 成本路径模 型最 大的区别。该模 型算法可 以利用计算机 自动完成 ，不受物流配送 网络 大小和 节
点的限制 ，并保证 算法 的正确性 。
关键 词 ：物流配送 网络； 时间价值 ；最优路径
中 图分 类号 ：F2 5 2．14 文献 标识 码 ：A 文 章编 号 ：1 67 2-474 7(20l 3)02—0019-05
A Logistics M inimum Cost Distribution Path M odel
and Algorithm Depending on Freight Tim e—-value
CHEN Wen．．qiang GU Yu-·lei
School of Economics and Management， Chang’an University，
Xi’an 710064， China
Abstract： A time—va1ue—dependent iogiSties minimum COSt admeasure path mode1 for a 1ogiSties
network was constructed．and i tS algorithm was studied．The model div／ded a delivery process
into tWO partS， that iS， the transportation and the 1oading and un1oading processes，
meanwhi 1e， the 1OSt due to the time de1ays in the two processes WaS considered． ThiS iS
tIle great difference from the other models．The elfiCient imp1ementatiOn was deSigned that
al1owed path computating on a realistie large-scale network without 1imit ing the transport
node number． The CorrectneSS of the a1gorithm WaS gurrantied．
Key words： LogiSties admeasure networks， value of time， the optimi zation path
收稿 日期：20I2-06．II．
基金项 目：中央高校 本科研业 务赞专项资金项 目 (CHDW201 I JC022)。
作者简介：陈文慢 (198I～)，男 ，安徽界首人，：1：学f_lI『士， K：安大学经符学院训：师 ，从事运输经济竹 研究。
19
交jln远输 I m“ 信息学报 20I 3 笫 2删
0 引 言
物 流 送 络 }1，物 流 送 向 1何 按照 一‘定
的 则选 择 最 优 踏 侄 ，完 成 物 流 需求 配 送 作 ，一一
足 _【JJ『究 青 的 币 课 题 ， 研 究 成 果 丰 富 。 例 如 ，
H．C．JokschI】 提 出 ⋯ 类 带 有 时 问 约 束 的 最 短 配 送 路
径 题 ， 并 给 出 了静 态 的规 划 方 法 ；G．Handier1 2]提
Ⅲ l『边 带成 本 约 束 的 最 短 配 送 路 径 问题 ，并 证 明 其
属 NP完 备 问题 ，并 给 了 一 个 对 偶 算 法 ：J．More
等 __Il提 出 了 一个双 日标 最 短 配 送 路 径 问题 ， 并 给 出
了 算 法 一 述 模 型 一般 为 定 常 需 求 模 型 或 为 静 态 路
径 模 型 ， 其 对 中 长期 物 流 配 送 网 络 的 规 划 是 有 效
的。但是，在现代 物流网络 中，南丁交通事 故、道
路拥挤 、天气变化 等偶发因素常引起物流配送网络
的 动 态 变 化 性 (OD 对 之 问 的最 优 路 径是 时 变 的 )，
此，利用传统静态最优 配送路径模型研究实际 问
题 叫’，容 易 导致 决策 错 误l4 J。 了：此 ， 本 文 充 分 考
虑 r动 态 出 发 时 问 利 运 输 过 程 延 迟 对 酉己送 路 径 选
择的影响，提 出了撼 于时间 、费用的双 日标决策的
动 态 物 流 网 路 配 送 最 优 路 径 模 型 。
1 问题分析
1．1 问题 表 述
本 义 所 述 物 流 配 送 网 络 是 。r城 市 道 路 网 组
成 的 物 流 网络 ， 由运 输 路径 ，物 流 配 送 节 点 组 成 。
丁物 流 配 送 需 求 特 点 ， 将 物 流 运 输 网 络 进 行 抽
象 。物 流 配 送 网络 被 拙 缘 为 矢量 ，物 流 配送 节 点
足 ·}l的节点 ，运输路径是 图中的线 ，配送方 向与
物 流 方 向一 敛 。 l是 一 个 典型 的物 流 配 送 网络 几
们 抽 象 譬， 1¨配 送 网 络 节 点 |v，运 输 路 径 A和 时
问 T构成 ，此 也可 以用 雨数 G：f(N，A，T)表示 。
kit何 物 流 送 网 络 g中 ，符 合实 际地 选 取 丁 动
念 }l、『 货 r¨ 的最优配送路 径 0_D(从 0点到达 D
点 )址r小 艾的 本 问题 。
1．2 问题 的解 决 思 路
彩 rj标 城 优 配 送 路 径 问 题 的 般 处 理 方 式 足
广 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一
【 i 一 ：
：
⋯ ⋯ ⋯ ⋯ 一 一 譬 !⋯ ⋯ ⋯ ⋯ ：
图 1 典 型 物 流 配 送 网 络抽 象
Fig．1 A typicaI di stributiOI3 network
把 多 目标转 化为单 日标 去求解 ，从而 使叫’问 、赀
用 相关的最优路径转化为单 日标最优路径 问题 。物
流配 送需 求 实现过 程 由运输 过程 利装 卸 过程 两 部
分 组 成 ， 所 以 ，本 文采 用 两 阶 段 分 析 法 ，把 最 优 路
径 问题 分 为 两 个 部 分 ，建 立 各 自模 型 ，最 后 联 合 分
析求解总 目标 (费用最小路径 )。
2 模 型构建
配 送 过 程 中 ，最 优 配送 路 径 选 择 往 往 是 南 多种
因 素 决 定 的 。但 时 间和 费用 一 般 是 决 定 最 优 配 送 路
径 的 主 要 影 响 因 素 ，并 儿 ，影 响 效 果 一 般 通 过 实 际
配送费用来 计量 。 由于物流需求 的 质性 ，同 一
种 服 务 反 映 的实 际 用 会 有 所 不 同 。为 清 晰 反 映 实
际 费 用 构 成 ，本 文把 实 际 用 分 为 客 观 用 和 货物
时 问 价 值 损 失 。所 谓 货 物 时 问 价 值 的损 失 ，是 指 物
流 需 求 没 有 住 规 定 时 问 内到 达 F1的地 ，使 货 物 失 去
一 定 时 问 价 值 。它 可 用 两 个 参 数 乘 积 (前 提 假 设 ，
时 间价 值足 途 时 间利 时问价 值损 失 系数 的线 性
雨数 )来表示 ，即货物 途时问与 货物 (出行时问
和 配 送 延 迟 )时 问 价 位 损 失 系数 乘 积 。
物 流配 送需 求实 现 全程 l11运 输过 程 和装 卸 过
程 部 分 组 成 ，实 际 赀 斤]也 町 以分 为 运 输 过 川
和 裟 卸 过 赞 川 。
2．1 运 输 过 程 费 用 模 型 函 数
运 输 过程 赞川 『t1运 输 客观 刚利运 输 问价
20
个货物时 问价值的物流州络最优配送路 模 型研究 艾慢 等
位损 失组成 ，运输客观 用 【!土可称 为运输 过 的固
定 赞 用 (燃 料 、 人 工 、损 耗 等 )，它 是 }f1运 输 技 术
济特性 决定的：运输 时间价 值损 失足货物对运输
时 问 延 迟 的价 值 缺 失 表 现 ，用 运 输 过 程 时 问 +货 物
运输时 间价值 损失 系数来 表示 。那么 ，运输过程 费
用可用 甬数 (1)表示 。
= m(，)4- m(，) (1)
式中： ?(r)——f和J之问路段上出发时间为f的
m类物 流需求运输过程 费用 ：
m(，)— — f和 J之 问 路 段 上 出 发 【f、】‘问 为 ，的
m类 物流需求运输 固定费用 ；
f m(f)— — f和 之 间 路 段 上 出 发 时 间 为 f的
m类 物流需求运 输过程时 间；
(，)—— 出发 时间 为 t的 m类物流 需求运输
时问价值损 失系数 (运 输造成 的时间价值损失系数
定 义 如 下 ：在 规 定 的 时 问 内将 货 物 运 到 目的地 ，运
输时 间价值损 失系数 为零。距 离货物失 去时 问价值
的时 间越远 ，由于运 输造成 的时间价值损失系数越
大 )。
2．2 装 卸 过 程 费 用 模 型 函数
如 运 输 过 程 费 用 一 样 ，装 卸 过 程 费 用 也分 为装
卸 过 程 固 定 费 用 (客 观 费 用 )和 装 卸 过 程 时 问价 值
损 失 。装 卸 过 程 固 定 费用 由像 装 卸 赞 、人 工 等 相 关
固定 费用 组成 ：装 卸过程 时间价值损失是 南 丁二装卸
时 间延迟 等而造成 货物 价值 的损 失，用装卸过程 时
问乘 以装 卸时问价 值损失系数表 示。裴卸过程 相关
费 用 函数 如I(2)所 示 。
( ml ：(，)+ (，) (，) (2)
式 中： ：(，)—— 出发时 问为 ，，m节点 i出发 ，
经节点 _，卸下 I、装上 2类 货物 运输到节 点 k过 程
中 的 赞用 ；
(，)— — 出 发 时 间 为 r， 由节 点 i出 发 ，
C h ．7”
-I‘点 卸 F 、装 2类 货 物 运 输 剑 节点 k过
巾 的 l定 赀 J干】；
I"nt2(，)— — n{发 时 问 为 ，， ⋯ 节 _i出 发 ，
节 点 ．，卸 下 、装 上 m2类 货 物 的 时 问 ；
(，)— — 出发 时 问 为 ，，卸 下 ml、 一 m2
类 货 物 的 时 问 价 值 的损 失 系 数 (狄 卸 造 成 的 l¨ 问价
值 损 失 系 数 定 义 如 下：在 规 定 的 时 间fi内 装 卸 ， 卸
时 问价 值 损 失 系 数 为 零 。距 离 货 物 失 去 时 问 价 值 的
叫 问 越 远 ， 由 于 装 卸 造 成 的 时 间 价 值 损 失 系 数 越
大 )。
2．3 最 小 费 用 路 径 模 型 函数
在 物 流 配 送 网 络 中 要 想 找 出最 小 赀 『{】路 径 ，物
流 配 送 需 求 实 现 赞用 模 型 必 须 计 算 经 由每 一 个 节 点
的运 输 相 关 赀 用 和 装 卸 相 关 费用 。 根 据 这 一 原 则 ，
整个运输过程费用模 型函数设计如式 (3)所示。
m( --
k
m
∈r(
in (， + } (3)
式 中： fm )—— 在 出发时 间为 f，由起点 i装 卸 m经
由节 点 ．，，并 由节 点 到 终 点 D 的最 小 赀用 ：
r(i)—— 节点 f的下一个节点 ：
此 模 型 最 明 显 特 征 就 是 把 整 个 配 送 过 程 的
定 配 送 费 用 和 时 间价 值 损 失 很 直 观 的联 系 起 来 ，并
且 可 以清楚 的表 明整个 配送 过程实 际赀刚的明细 。
3 模型 求解
3．1 算 法
最 小 配 送 费用 路 径 求解 采 用 倒 推 法 l丰1终 节 点 D
向 前 推 进 ，具 体 步 骤 如 下 。
(1)检验 。(，)位 ；
如果 。(，)≤{ 舭mI ：(，)+ (，)+ (，)}，继续；
如 果
’(，)>{ (，)+ (，)+ (，)}
2l
交迎运 输 I l信息学{t土 20l3 第 2划
令 ≯(，) { 嚣 ：(，)+ (，)+ (，)}
贝U节点 七为 最 优 路 径 的⋯ 个 节 点 。
(2) 复 步骤 (1)，找 出 七节点 的 上 ⋯个 最 优
路 杼 节点 f一’( ；
(3)重 复 步 骤 (2)， 直到 找 出最 优 路 径 的 所 有
的 节 点 ：
(4)结 束 算 法 。
此算法从终节 点 向前推进 ，算法过 程其实就是
榆 查 一 个 节 点 七前 一 个 节 点 z-一’(七)是 否 存 一 条 路
径 使 节 点 七到 Z．一’( )的 赀 用 最 小 ， 如 果 条 件 满 足 ，
r一 ( )是 条 件 点 之 一 。 依 此 类 推 ，直 到 找 出所 有 符
合条件 的节 点，这些点组成 的路 径就是 时间相
关 的物流 网络最 小配送 l费用路径 。
为 保证算 法 的 合理性 ，必须对 参数 进 行合理
设 置 。
3．2 正确性 检验
算法 的每个 阶段 ， 目标 (，)值只 能是有 限数
或 无 限 数 。如 果 (，)值 是 无 限 数 ， 意 味 着 配 送 费
用 无 穷 大 ，此 节 点 和 其 对 应 的 下 一 个 节 点 之 问 路 径
不 通 。如 果 目标 函数 值 是 有 限 数 的 话 ，表 明 此 节 点
至 少 是符 合 条 件 的 节 点 之 一 。
如果 目标 函数 位为有限数 ，则 目标 函数形式为
(，) 嚣,m2(f)+ (，)+ (，) (4)
I1必 满 足 下 几 种情 形 之 一 。
① (，)和 (，)所涉及的节 点没 有变化 ；
② ：(，)节点 j下一个节 点经 过节点 ，j节点
可 能 发 生变 化 ：
③ ≯(，)节点j下一个节点经过除了节点七的
任 意一个 节点 ，经过 的 点顶替节 点 七；
④ (，)节 点 七是节点 j的上⋯一个节点 ， 是
点 七还没被枪验是否 是最优节 点。
是情 形① 或② 或③ 发生 ，则进 入算法步
(2)：
『』Il果发生情 形④ jCD，则 rj标函数 为
(，)>{ 苏,m2(，)+ 【，)+ (，)} (5)
那 么进 入算 法 步骤 (1)。
无论模 型算 法还 足 确性 榆验，均可 以 汁算
机环境 下 自动实现。
4 实例证 明
假 设物 流 配送 网络 图 2所 示 ，从 。 点 }={_j发进
行物流配送 ，D点集结补养 ，综 合考虑运输 相关赞
用 和 装 卸 相 关 赞 用 ，求 解 最 佳 配 送 路 径 。利 用 Netlog
软 件，编写程序 ，模拟运算 ，结果如下图 (黑粗线 )
所 示 。
图 2 最 优 物流 配送 路 径
Fi g．2 The optimaI Iogi stics path
图例 中黑色 区域 是备选 路 径和 ： 点组成 的 ■角
络 ，黑粗连 接线 表示 算法选 择 路线 ， 最优 配送
路 径 。
5 结束语
本 文 根 据 物 流 配 送 网络 中 影 响 物 流 配 送 的 的
多因素 ，构建 _r 丁货物 时 价值的物流删络最
小 配 送 赀朋 路 径 馍 ，依据 物 流 送 的 决 定 豢是
1 货物时 问价值的物流 『圳络城优 送路 帧 型 ，宄 陈义慢 等
实 际 配 送 川 ， 从而 将 多 n标 最 优 路 径 转 化 为 最 小
配送 赀川路径 问题 ，给 出模 型的算法 ，验-【iI ．『算法
参考文献
【I J Jokson H．C．The shortest riute problem with
constraints[J]．Journal of Mathematical Analysis
and Applicatilon．1996，(14)：l91·197．
【2】 Handier G A dual algorithm for the constrain
shortest path[J]．networks．1 980，1 0(2 o)：293-3 1 0．
【31 MORE J．，Murthy I．A parametric approach to solve
constrain shortest path problem[J】． European
Journal of Operation Research．I 99 1，53：8 I-92．
【4】 Newall Q F．Flow on transportation network[M[．
M IT Press．1 980．
【51 ziIiaskopoulos A．K．and Wardell W．An intermodal
optimum path algorithm formultion modal networks
的 il!确 性 ，论 文最 后 利 门1 Netlog软 件 榆 验 了模 趟 的
jE 性 ，结果显示 ，模 型及算法是可 行的。
【6】
【71
with dynam ic arc travel times and switching
delays[J]． European Journal of Operational
Research．2000，1 25：486 502，
Jourquine B．and Beuthe M ．Transpo rlation policy
analysis with a geographic information systemlJ]．
The Virtual Network of Freight rranspOrtatiOn in
Europe， Transportation Research． I 996， 4C：
359-371．
陈文 强 ，吴群琪 ．时 问棚 荚 的运输 网络 最 小 费用
路径 模型 及算法 [J】．铁 道运 输 与经 济 ．2009，5(31)：
11．14．
(中文编辑 ：吴继屏 )
上接第 18页
【2】
【31
【41
【5】
【6】
f7】
Huanyu Yue，Albert Gan，Ike Ubaka．A decision
model for bus-only and HOV lanes on freeways[J]．
Transpo rtation Research Record。2003：l 20-l 24
Jaimyoung Kwon，Pravin Varaiya．Effectiveness of
California’s high occupancy vehicle (HOV)
system[J]．Transportation Research Part C l 6，2008：
98-1l5．
易汉 文 ．美 国 2005年 城市 机动 性报 告 摘要 【D】．加
利福 尼 亚 ：美 国加 州交 通 部 ，2005．
毕仁 忠 ． 国外 HoV 专用 车道 的现 状 及发 展趋 势
【J】．公路 ， l997，(6)：34-37．
陈 玮 ，陈 自磊 ．将 HOV 优 先 引入 我 国城 I．1=『交
通 规划 的管 理 【J】．城 市规划 ，2003．27(6)：28-30．
李鹏 色，韩 舒 ，林 航 飞 ，HOV车 道 在上 海城 市
交 通 管 理 中 的应 用 探 讨 [J】．交 通 与 运 输 ，2007．
(12)；6-10．
【8】 詹 嘉 ，潘 晓东 ，高 昂．HOV车 道 的设计应 用
研 究【J】．变通 与运 输 ，2007。(7)： l4．18．
【9】 南 京市 交通 规划 研究 所 ．2Ol0年南 京市 交通 发 展
年 度报 告【R】． 南京市 交通 规 划研 究所 ，2 0l0．
【l0】王志彪 ．VISS1M交通仿真适应性研究【D1．北京：
北 京交 通大 学 ，2006．
【ll】California Department of Transportation，Division
of Trafnc Operations．H igh Occupancy Vehicle
Guidelines【EB／OL】．2003．
【l2】中国建筑工业出版社．城市公 交通规范【s】．北
京： 中阉建 筑工 业 出版 祉 ，l997．
(中文编辑：刘她婷 )
