i=
1, …, N -
1; j ∈ N i;
k ∈ N i+ 1 ; l ∈ J ( 5)
x , l i, j ,i+ 1, k
r
l, i,
u j
∈
{
0,
1}
,
i=
1, …, N -
1;
j ∈ N i; k ∈ N i+ 1; l ∈ J ; u ∈ J ( 6) 其中, 目标函数以整个运输过程中的运输成本最少
s. t.
N- 1
∑∑ ∑ ∑t x + l
l
i, j ,i+ 1, k i,j , i+ 1, k
i= 1 j ∈N i k∈N i+ 1 l∈J
M- 1
∑∑∑∑ l,u i, j
rl, i,
u j
≤
T
( 4)
i= 1 j ∈N i l∈J u∈J
q
≤
f
l i, j, i+
1, k ,
N N = 1;
T : 从中心点到目的地容许的时间期限;
J : 可供选择的交通工具集合;
I : 所有的要经过城市的集合;
q: 货物的运量;
M : 一个充分大的惩罚因子.
N- 1
∑∑ ∑ ∑ Z = m in
x c + l
l
i, j , i+ 1, k i, j , i+ 1, k
i= 1 j ∈N ik∈N i+ 1 l∈J
N- 1
N- 1
∑∑∑∑ ∑∑∑∑
r d + l, u l, u i, j i, j
(
- l, u
i, j
1) M
i= 1 j ∈N i i∈J u∈J
i= 1 j ∈N i l∈J u∈J
∑ ∑ ∑x = l i, j , i+ 1, k
1,
i=
1, …, N -
1 ( 1)
j ∈N ik∈N i+ 1 l∈J
2005 年 9 月
的点( D) 到虚拟的城市( D' ) 之间的时间和费用均 设为零, 运输能力设为一个充分大的整数. 则原问 题的求解可以转化为: 在不超过运输期限和能力的 约束的前提下, 求从( O → D' ) 的最短路径。
此问题是一个 N P 难题, 很难得到全局最优解 或满意解, 而本文用设计改进的遗传算法对其进行 求解, 取得了较好的效果. 3. 2 对于非相邻阶段之间存在城市有路径可走的
第
25 卷 第 3 2005 年 9 月
期
Jo
u
rnal
of
天津 T ianjin
师 范大学学报 N or mal U niv ersity
( 自然科学版) ( N atur al Science
Editio n)
V ol. S ep.
25 N o . 3 20 05
文章编号: 1671-1114( 2005) 03-0066-04
段的第 k 座城市选择第 l 种运输成本.
f
l i,
j,
i+
1,
k
:
在第
i
阶段的第
j
座城市到第 i
+
1阶
段的第 k 座城市选择第 l 种运输能力.
d
u, i,
l j
:
在第 i
阶段的第j
座城市由第
u
种交通方式
转换到第 l 种交通方式的中转费用.
: u ,l
i, j
在第 i
阶段的第
j
座城市由第
l
种交通方式
( 2) 假设城市 A 与城市 B 有弧连接, 则由 A 扩 展的 g 个城市与由 B 扩展的 g 个城市两两有弧连 接, 假设 A 与 B 没有弧连接, 则由A 扩展的任意个城 市与 B 扩展的任意个城市都没有弧连接, 同一个城 市扩展而来的点与点之间不存在连接弧.
( 3) 各条弧上的权重, 分为 3 类: 费用权重, 时间 权重, 能力权重.
数变量 0 或 1.
3 模型的求解
通过 虚拟一个运输网络, 将原问题转化为一个 带时间约束、能力约束的最短路径问题, 然后利用遗 传算法对其进行求解. 3. 1 构造运输网络图 G{ V, A}
方法如下: ( 1) 除始发点( O) 外, 将其它的 g 各 城市分别扩展成各城市( 每个城市代表一种运输方 式) , 且这个 g 城市还处于原来的网络阶段, 然后, 虚 拟一个最终的目的地( D' ) .
Abstract: Fo r st ag ing t ransport at io n net w orks, a opt imal com binat io n model of m ul tiple t ranspo rt ation mode w as pro posed. By constr ucting a virt ual t ransport at ion netw or ks, t he orig inal problem was convert ed t o a specif ic short est pat h pr obl em . A genet ic algo rithm f or solving t his pr obl em w as designed and applied, an example t o this pr oject , w hich indicated t hat this met ho d w as f easible and ef f ect iv e. Key words: g enet ic algo rithm ; opt imal combinat ion m odel; virt ual net w orks
∑∑∑r l, u i, j
=
1,
i= 1, …, N - 1 ( 2)
j ∈N i i∈J u∈J
x + k i- 1, j , i, m
x
l i,
m,
i+
1,
n≥
2r
l, i,
u j
,
i=
2, …, N -
1;
j ∈N i+ 1; m∈N i ; n∈N i+ 1; l , u∈J ( 3)
1 问题的提出
假设一个物流企业将一批货物从货物的中心地 点( O) 经过一个运输网络运送到目的地( D) , 在任 意有路相通的城市之间都有若干种运输方式( g 种) 可供选择, 并且在有路相通的城市之间运输方的运 输时间、运费、运输能力不尽相同. 当在一个城市从 一种运输方式转换到另一种运输方式时, 需要一定 的中转时间和中转费用, 并且在整个运输过程中的 总时间不能超过运输期限( T ) . 对于特殊的货物运 输同时要考虑到其转换方式的可能性. 在考虑上述 各种因素的前提下确定最佳的运输组合方式, 使得 总运费最低.
为 目标, 它由 3 部分组成: 运费, 中转费用, 惩罚函
数. 模型的约束条件: 表示在相邻阶段的城市之
间, 若存在路径, 则只能选择一种运输方式, 即运量
不能分割; 表示在第阶段的第座城市只有一次运
输方式的改变; 确保运输的连续性; 表明货物
必须在规定的期限内运到; 表示货物的运量不能
超过某种运输工具的能力; 表示决策变量是取整
Optimal and Solution of Multiple Transportation Modes
ቤተ መጻሕፍቲ ባይዱ
CH E N X iang -dong , L I U Y an-liang, WA N G Peng-tao, N I NG P ei-hong
( Dept . of C om put er Science and E ngineering, T ianj in U nivers it y of T echnol og y, T ian jin 300191, Chin a)
多种运输方式模型优化及求解
陈相东, 刘彦良, 王鹏涛, 宁培红
( 天津理工大学 计算机科学与工程系, 天津 300191)
摘要: 对可阶段化运输网络, 提出了将路径选择与交通运输方式相结合的组合优化模型. 通过虚拟 一个运输网络, 转化为一个与原问题等价的最短路径问题, 并设计了相应的遗传算法对其求解, 通 过实例计算表明, 该算法对该问题是可行和有效的. 关键词: 遗传算法; 组合优化模型; 虚拟网络 中图分类号: U 116 文献标识码: A
收稿日期: 2005-04-05 基金项目: 天津市教委自然科学基金资助项目( 20030618) ; 天津自然科学基金资助项目( 045600511) 第一作者: 陈相东( 1980- ) , 男, 山东省德州人, 硕士研究生, 主要从事遗传算法方面的研究. 通讯作者: 王鹏涛( 1949- ) , 男, 天津市人, 教授.
费 用权重 = 两城市间的运费 + 中转费用; 时 间权重 = 两城市的运输时间 + 中转时间; 能力权 重 = 两城市间的某种运输工具的运输能力.
为计算方便, 将没有弧连接的城市之间的运费、 时间设为一个充分大的整数, 运输能力设为零, 由目
·68·
天 津 师 范 大 学 学 报 ( 自然科学版)
第 25 卷 第 3 期
陈相东 , 等: 多种 运输方式模型优化及求解
·6 7·
2 模型的假设与符号的说明
2. 1 模型假设
( 1) 运输网络可阶段化, 同一阶段和非相邻阶
段之间的城市之间不存在路径.
( 2) 运量在某一对城市之间不能分割, 即在某
一对特定的城市之间, 若存在路径, 则在这对城市之