运筹学在交通运输领域中的应用与发展‘
何世伟宋瑞胡安洲
北方交通大学交通运输学院，北京100刀不
摘要
本报告介绍了运筹学与交通运输之间的关系、交通运输领域(特别是运输规划与管理领域)
中的运筹学间题、算法理论的发展及在交通运输领域中的应用.
关键字:交通运输，运筹学，规划，管理，优化
APPlieationandDevelopmentofORinTransPortation
}IEShiweiSONGRui
Sc人001qf乃叹所e翻介an、尸。了、tat:o。，No，，thor，，J乞aot云几g
Anzllou
U几ivor、‘t夕，Be勺云几91000不不
Abstraet
JiltllepapeJ，，thel，elatioilsofopel·atioilal，℃seal，eh(OR)andti·ansportationareilltro-
(lueed.Tlzedeveloplne，itofORprolole;，15andtheiralgorithmsintransportation(espe-
eiallyintransPortatiollplanningandmanagement)arepresentedandtheapplieations
aread〔lressed.
Keywords:Tl，axisportation，OPeratiozlalreseai，eh，Planning，Management，Optimiza-
tion
怪1运筹学与交通运输之间的关系
(劝运筹学与交通运输之间的关系可谓源远流长
大家知道，运筹学的方法论比较系统地引入是丘奇曼、阿可夫和阿努夫在1957年的
运筹学导论一书，但早在1939年，前苏联数学家康特洛维奇在其编著的《生产组织与计
划中的数学方法》一书，就研究了运输和下料等问题，事实上，从运筹学诞生之日始，
运筹学就与交通运输有着密切的联系，并且今天这种关系得以不断的巩固与发展.
(2)交通运输领域是运筹学发展的重要温床
‘国家自然科学基金(No.79700002，No.79800o01)与霍英东青年教师基金(No.71074)资助148何世伟宋瑞胡安洲
交通运输领域，为运筹学间题的研究，提供了大量的案例背景，由于这些背景为大
家日常生活所熟识、利于理解且一般具有比较重要的实用价值，一经提出，发展很快，
有的现已成为运筹学领域的重要问题和重要组成部分。如经典的并为大家熟知的运输间
题，再如最长(短)路间题、网络流问题(最小费用单商品流间题、多商品流间题)等，以
及旅行商TSP问题，这些问题都非常容易在交通运输领域找到广泛的应用实例，此外，
还有稍专业的如车辆运行径路问题、运输规划有关的选址问题，时间表问题，运输调度
问题，车辆配装问题，运输能力问题等等.对这些问题的研究，都曾积极推动了运筹学的
发展与进步，如关于运输问题的西北角算法，关于最小费用单商品网络流问题的网络单
纯形算法、瑕疵算法等，再如遗传算法中针对运输问题做的特殊编码方式、算子设计等
(参见Micllalewiez2.GAs+DataStl，u(:tures=E、01，ltiollprograms).
(3)运筹学为交通运输规划与管理科学化提供重要的支持手段，带来巨大的社会经济
效益。因为，运筹学本身就是
要解决如何运用现有的资源(如人力、机器小时、原材料等)
安排生产，使产值最大或利润最高;或者，对于给定的任务，如何统筹安排，以便用最少
的资源消耗去完成。因此，只要运筹学方法在交通运输领域应用得当，就能够实现其优
化资源、降低消耗、提高利润的目标，创造巨大的社会经济效益.
尽2交通运输领域中的运筹学问题
刚才提到交通运输与运筹学关系紧密，那么交通运输领域中到底存在哪些运筹学问
题呢?应该说，交通运输领域中的运筹学问题存在多种不同的分类标准，如按问题的性
质划分、按求解方法划分、按发展时间进程划分、按行业应用划分等，这里，为了便于
大家理解，我们把当前交通运输领域需要或正在研究的问题分三类:称为原问题(基本间
题)、领域重要问题、领域一般问题和其它问题。
钾.1原问题·(基本问题)
什么是原问题，即历史形成的，有一定运输背景，并被不同领域广泛认可(包括国内
外重要数学、运筹学等杂志大量登载)约定俗成的一些问题，当然这些问题本身也容易组
合换化，产生变种，如运输问题，旅行商‘拐P问题、最短路问题、网络流问题等，车辆
运行径路何题有些专业色彩，但由于其广泛性实质也可列入原问题.
对原问题的研究一般主要侧重在模型的算法求解方面，并不关心形成问题和解的实
施，因此，有的研究成为运筹数学的一部分。应用实例:
车辆路径问题(Vel:ieleRol，士，1119prolol。::1)!l)〔2{
不妨令图G=}丫几一勺，其中v二扫…，心为节点集，表示城市(或货栈)，而点l
表示中心车站，八为联弧集。对于每一弧(f，力有一非负距离矩阵C二(c、、)、仇J可视为
旅行费用或旅行时间;另外，假定中心站有二辆可用车，其中，二:三二三。互，。当
，，，:=，，，。;时，?了;称为固定，当，，，:=l且，，，二，，一z时，川称为不固定.但，，，不固
定时，对每一辆车的使用有一联系的费用f，为简化问题，我们假定所有的车辆相同且
有相同的装载能力，此外，还有如下约定:运筹学在交通运输领域中的应用与发展149
(l)U\{l}中每一城市将正好被一辆车访间一次;
(2)所有车辆路径都始于并终止于中心站;
(3)需满足某些边约束，常见的边约束包括:
①载重量(容量)约束:对于每一城市(或货栈)‘>l，有一个非负重量(或需求).l、与
之相联系，车辆载重不能超过其最大能力，该类问题又称为cvRPS;
②每一径路上城市数(或货栈)限制，不允许超过某一常数q;
③总运行时间约束，路线的长度或车辆总运行时间(线路运行时间十中间停车时间)
不允许超过规定值L，该类问题又称为DVRPs;
④时间窗口约
束:城市(或货栈)乞只允许在给定的时间窗范围内访问;
⑤优先关系:城市(或货栈)‘必须先于城市(或货栈)j被访问.
还有别的一些约束情况可参见GoldenalldAssad(1985)书.
变异情况(考虑更多约束):(l)车队数(一个车队、多个车队、不定车队);(2)每
个车队车辆数(土辆，多于l辆);(3)车辆类型湘同、不同);(4)供求类型(确定、不
定);(勺需求位置(边、节点、混合型);(6)网络类型(无向、有向、混合);(7)其它
时间规定(有、无);(8)费用函数(固定、随时间变化、模糊、随机);(9)作业类型(有
倒装、无倒装);(J0)车队位置(活动、确定);(川送达程度(全部、部分).
目标函数(总里程最短、运费最小、人因素、最少车辆数、缺货损失、停车损失等)。
愁2.2领域重要问题
领域重要问题是指与交通运输领域运输规划、生产管理关系密切的重大间题，如时
刻表问题(用于运营规划，铁路、公路、航空、水运等都有这类间题)，调度问题(运营组
织)，车流组织，车辆配装问题，运输能力问题等降8]，这些问题往往对本领域理论发展
有重要作用，被交通运输类刊物大量登载的，行业资金大量资助的研究问题，行业有较
多研究机构与人员从事该类问题研究，但非该领域专家少有介入，如智能运输系统相关
的ITS有关问题(已经产生对社会生活的重大影响)，高速铁路研究问题等。应用实例:
(l)路网优化设计问题(公交、现立体交通与地铁、轻轨、高架独轮共同设计)
目标为:总交通时间达到最小、总出行时间最小、成本最少
乘客选择乘车线路依据:①选择从矛到j所花交通时间最少的线路;②选从i到j中
转次数最少的线路;公交线路选择的基本原则:①线路的非直达系数小，亦即尽量使线
路走最短路;②线路上直达人数应尽量多，以减少中转;①全线路满载系数不宜过短，过
短会增加中转，并使车辆在端点站的停时增加;亦不宜过长，过长对调度管理不利。
约束条件:①起终点位置约束;②非直线系数约束;③长度约束;④起终点容量约
束、⑤道路容量约束;⑥中转量约束;⑦最大乘次约束等。
(2)车流组织问题(铁路!
解决货物怎样从出发地运送到目的地的问题。包括运什么货物，怎么组成列车，列
车运行径路，列车在哪个车站解体并重新组成新的列车，目标是总运送时间最短、运输
费用最小、运营收入最大、货主满足度最高等。约束包括:线路运输时间约束、车流不可150何世伟宋瑞胡安洲
拆散约束、车流合并约束、编组站解编能力约束、线路能力约束等。
(3)时刻表问题(铁路)
解决交通工具运行时间安排问题，如规定列车(或车辆)车站到发时间，交会越行方
式，机车运用，乘务派班等。
目标总旅行时间最短、运用机车数最少、旅客和货主满足度
最大、成本最低等.约束包括，线路运行时间约束、车站列车到发间隔时间约束(5种)、
列车单独占有线路约束、列车禁停约束、运行径路约束(2种)、机车乘务组工作时间约
束、施工天窗约束、列车到发时刻特殊要求约束、车站到发线约束。
(4)调度问题(铁路，柔性优化)
解决日常运输组织指挥问题.如空车分配、机车运用、列车运行调整、车站作业安排
(包括调机运用、到发线运用、车流接续协调，目标是车流在车站停留时间最少、出发正
点率最高，可转化为排序网络流间题)等。
(5)ITs问题(实时动态时变问题，综合诱导与控制)等.
铃.3领域一般问题
领域一般问题主要是一些与交通运输领域有关，但应用范围比较专一(甚至可能为
某一行业某种情况下所独有)的一些非主流性问题，如某一具体车站设计优化，开行某种
新的独轨双人车(韩国)，旅客顺路搭车问题(香港)等.值得注意的是，在一定条件下，
原问题、领域重点间题、领域一般问题可相互转化。
芬2.4其它问题
其它与交通运输领域有关的问题.
93算法理论的发展及在交通运输领域中的应用
计算机与算法理论的发展对交通运输领域中运筹学问题的解决起到积极推动作用.
多数运输类问题(连续或离散)具有大规模、非线性、多目标、多约束特点，算法理论的
发展对解决这些问题起到积极推动作用。应用实例:
(1)车辆运行径路间题(重要刊物年均30一40篇)[l〕{2]
80年代以前
精确算法:
①Setpartitioninga:ldeolu，11ngenora七1011(BalinskiandQl，an〔It，1964)
②Dynamiep:ogrammi，、g(Eiloll，\Nratson一Gal、dyandCI、ristofides，10了一)
启发式算法:
①TlleClarkea」，ld助19}ItAlgo，·i山，1。(1964)
②Thesweepalgorithni(WI.ell，1971:\Vrel飞alldHollid恻，1972;GillettandMiller，1974)
③TheChristofides一人11，190221一肠t，11t「wo一l)111·asealgoritlll二(1979)
80年代运筹学在交通运输领域中的应用与发展151
①TheassignmentIowerl)oun〔1al:darelated!〕raneh一boundalgorithm(Laport，入/Iereure
a，l(1Nober‘，1986)(精确)
②TI、ek一degreeeentertreeandarelatedalgori(h，n(Cliristofides，MingozziandTOtl，，
1981)(精确)
洲年代
A七a6一seal.el、algorit更In、
(Ge，飞dreal，，Hert，2andLaporte，1991)、((子en〔lreau，HertzandL叩orte，1994)、
(C〔)rdea、，，Gelldrea飞卜andLaporte，1997)、(pot、inan〔1Jean一Yves，1997)(Barbarosogl、、，
G，‘lay，1999)
5121:一llatedallneal一119
(rreodorovie，etal.，1992)(Bree〔lal。，1995)(NakaeukiandThangiah，1997)
Ge一、etieAlgorithms，EvolutiozlaryAlgoritlim
(Kra，iear，Skrlee，pril〕ieevicandBlag。，lac，1995)(Berger，SaloisandBegill，1998)(Oelli，
Via，，
，，aDr，，，::，1、o，，da，ldVieto，·，1998)
ABrallel卜az]d一eutalgoritllln
(Araqlle，I丈11dva，Morillalldpek，，y，1994)
Stoel一astiean(If一lzzytheory，
(Bastian，etal.，1992)(Laporte七al.，1992)(Bertsimas，etal.，1993)(Kagaya，Kikuelii
a“dDonllelly，1994)
(2)公共交通网优化1’M题12}13〕
启发式、多目标混合整数分数规划(入{、，ltiobjeetive，nixedintegef11，learfl.aCtiollal
progra，，11”g)，〔’0111，“1，，Ge，‘eratio，1、智能计算方法(ANN，(;A，sA，EA)等。
部分相关文献:(G、，pta，1981)，(\叭·e，1，1994)，(21飞u，1904)(Linl，一‘)95)，(Czyzad，
1叨5)，(Vi.jayal’aghavan，1995)，(Costa，1997)
(3)车流组织问题叫阎
分枝定界算法只能解决11个支点站直线方向整数规划、以后发展了二次。一l规划模
型及网络拓扑分解算法、线性逼近算法、厂ra}〕、，searell和SimulatedAnlleali，19方法，解
决路网规模突破到双方向近40个支点站，算法本身包括技术站编组计划间题、装车地编
组计划问题、技术站与装车地编组计划综合编组问题、技术站与装车地编组计划与车流
径路间题综合优化、增加多约束(线路、车站能力)非线性费用优化间题.
部分相关文献:(Bodilletal.，1980)、(Assad，1983)，(VanDyke，1986)，(Newtol，，1996)，
(C{rari，lieetal.，1984)，(Haglialli，1989)，(I丈eato，1，1989，1992)，(Tellg，1996)，(Petersoll，1970)，
(H:，，ltleyotal.，1995)，(Gor，:la，1，1998)
(勺时刻表(运行图)问题网
铁路运行图间题的算法研究有三种思路:一是研究精确算法，1992年在西门子中型
机上，用分枝定界算法计算10*10，10(车站数，上行列车数*下行列车数)的单线列车
运行图问题的时间是1天，有博士生企图用精确算法解决这个问题，论文搞了10年，最152何世伟宋瑞胡安洲
后也没有解决得很好，国外报道情况与我们类似，这个例子说明，运行图问题由于属于
NP_C，完全依靠传统运筹学手段是很难处理的，那么，现在采用遗传算法、改进算法上
下解+启发式，ColulnnGelle:atioll方法处理，在一些国家取得成功，但模型相对简化，
运用研究思路二是模拟人工，建立大量递归逻辑关系，这个思路目前在我国铁路计算机
编图实用化方面取得比较好效果，目前能处理2000多列车、600多车站的网络运行图同
时编制问题(目标是两万列车，6000个车站)。思路三是建立专家系统，如日本高速铁
路，这不属于我们讨论范畴。
部分相关文献:(D.Jovano、厂iean〔11，.‘l‘Ha，、ker，l‘)90)(Jovallovieandp·T·Harker，1991)
(几五1’a盯，P.T.HaJ.j二ra，，dB.Ch。;.，]，gJ夕{Cal’0y，J994)(P.T.Ha1’l’eralld5.Hollg，P，
1‘)94)(J，入1.p.Boole，·，1995)(M.Ca，·e洛厂all〔1D.I·()ekwoo〔l，199
5)(C.L.工I，1，ltley，D.E.Browx，
D
.
]刃.Sal〕pi，lgtonal，dB，p.入{arkowiez，1995)(A.111991115，E.Kozalla，ldL.Ferreira，1996)(
5
.
卜’.Hallowellall(1P.1”.Ilal·ker，199(3)(M.且.Bussieek，P.Kret，zerandU.T.211、，，ner，1飞。11，1，
1996)(入1.Fisel，ettial飞dl，.厂rotll，1997)(A.Higgin、，E.I又oza，1alldL，Ferreira，1997)(M.F.
Go:，11a，1、]998)
侧车站调度问题闭
车站调度间题的算法研究与运行图类似，也有研究精确算法、模拟人工编制和建专
家系统三种思路。这个问题我们刚才说了属于排序网络流问题，就是车流分配与车列解
编顺序有关，算法国内有带分枝定界的排序十网络流算法，遗传算法，启发性方法，遗传
算法在处理调度问题的模糊与柔性问题上，显示了充分的优越性。此外，国外如普林斯
顿大学提出动态递归控制思路也引起人们极大重视，其博士论文曾被评为交通运输领域
年度优秀博士论文。
部分相关文献:(E.R.potorso:1，z，了了)(F.(‘lover，D.Karlley，D.I丈11119:二al，a;ldl飞.
R，，ssell.19了8)(V.B，Me，ldi飞·atta，19吕l)(M.A.叭，rnquistandM.5.Daskill，1982)(W.
\块r;lor，1983)(T.C，·ai;lic，J.A.价rlallol。，l〔]1.入1.Ro，，sseau，1984)(T.5.Cliel、nlallan〔l工1.
D
.
Sllerall，1985)(R.E.Hl，gllesall〔1W.B.f，o、vell，1985)(P.J.Detax。，ldT.G.〔‘rai，，ie，
]987)(J
.
DqianallolT.H.Pal’tri(、k，198至))(5.YogaralldFraeisic〔)，1989)(D匀anJovanovic，
1990)(I咬.C.〔’11111，1990)(Y.A.I丈。、kosiolis，19‘)O)(J.B.Georgealld人J.A.TI，l、，飞ql，ist，
1991)(B
.
D
.
Robert，1994)(Ile，1996)(卜I。，1997)
写4存在的问题、机遇、挑战与展望
前面我们介绍了交通运输领域存在的运筹学问题，及算法发展对运筹学在交通运输
领域中应用的推动，交通运输与国民经济发展和每个人日常生活息息相关，而且我国交
通运输正处于大发展时期，每年公路、铁路数一百亿的投入，对运输规划与管理都提出了新
的更高的要求，传统的交通运输组织管理方法，正发生深刻的变革与变化，原来重要的领
域问题，现在可能被新的更加迫切的研究问题取代，如关于ITS(I。比lligell，」‘1’l.al1、l)o1撇ti。11
Syste叫研究，对交通运输流的优化规划、设计、诱导与控制，在原来静态交通流问题基
础上，进一步发展了实时动态交通流的理论。又如列车时刻表问题，原来主张均衡运输，运筹学在交通运输领域中的应用与发展153
旅客与货物列车发车点要均衡，现在大量开行的夕发朝至列车，把这种均衡性破坏了，
应该如何组织列车，这是新课题，现在客运专线组织问题，再如车流组织问题研究，原来
主要倾向于交通运输系统内部的组织管理优化，现在根
据市场需要，提出诸如快运列车
开行组织间题，另外，方法进步了，一些不明显的间题又浮出水面，如编组计划的二次参
数准确性问题.在调度领域，如铁路投资25亿建立了全世界最大的信息管理系统，北京
公交投资3000多万建立公交调度信息系统，那么应如何利用这些信息进行调度指挥，这
涉及调度优化的实用化问题.
可以说，新的时代从应用领域提出大量新的运筹学问题，这些问题涉及开放复杂巨
系统建模，具有智能化、综合化、集成化、并行化、多层次、多目标(人性目标、环境目
标、柔性目标)、动态决策的特点，也需要运筹学科与其它学科的交叉融合，以进一步推
动运筹学科在交通运输领域的应用与发展。
参考文献
!1」G
.
1·aporte，Thevehieleroutingprobleln:anoverviewofeXaCtandapproximatealgorithms，
Joux:、alofOpel，atioxlalReseal℃11，59，1992.
【2〕宋瑞，ITS运输管理模式与决策优化的研究，北方交通大学博士后科研报告，1999，北京.
13〕Lj，:::、，、dN.5.于Ic，:g，Op‘j。，al，·ot，龙ingalgoritlimsforpul〕lietransport，TransportationScienCe，
29，No.l，1995.
l刃朱松年等，车流组织综合优化，铁道学报，199:3·
[sl李致中等，铁路运输管理的数学模型及算法，华中理工大学出版社，1995·
[61Jea，卜Fra，ieoisCo，，deau，A51，，、veyof01〕ti，，iizatio，1Inodelsfortrainrot，tingandselle山111，飞g，
TlallsPort，atioliSeie，、ee，32，(1998)，No·4.
[=l何世伟，铁路枢纽调度决策支待系统及其优化方法的研究，北方交通大学博士后科研报告，1998，
北京.
[s]胡安洲等，关于铁路运输能力间题的系列研究，铁道经济研究，(199勺，N。·L