长安大学学报（自然科学版）060320

	长安大学学报（自然科学版） JOURNAL OF CHANG'AN UNIVERSITY(NATURAL SCIENCE EDITION) 2006 Vol.26 No.3 P.80-83

基于空间填充曲线和动态规划解的定位路线问题

胡大伟　胡勇　朱志强　

摘　要：定位路线问题(LRP)是物流系统中一个重要问题,因其NP-hard属性,当节点数较多时精确解不宜得到.提出了单设施定位路线问题(SDLRP)的数学模型,并通过Lingo程序给予了检验.基于求解该模型的复杂性,进而提出了一种启发式解法,即利用空间填充曲线(SFC)构造初始解,同时实现设施定位,以保证初始解的质量;之后运用动态规划的方法确定最优车辆配置,并通过2-opt对路线进行改进.最后,通过实例验证了该方法的快速有效性.
关键词：交通工程;LRP;空间填充曲线;动态规划;算法
分类号：U492.313　文献标识码：A
文章编号：1671-8879(2006)03-0080-04

Solving Location-Routing Problem Based on Space Filling Curve and Dynamic Programming

HU Da-wei　 HU Yong　 ZHU Zhi-qiang　

基金项目：甘肃省交通科技项目(2171-2004854)
作者简介：胡大伟(1963-),男,北京市人,教授,博士研究生.
作者单位：胡大伟（长安大学,汽车学院,陕西,西安,710064）　
　　　　　胡勇（长安大学,汽车学院,陕西,西安,710064）　
　　　　　朱志强（长安大学,汽车学院,陕西,西安,710064）　

参考文献：

[1]林岩,胡祥培,王旭茵.物流系统优化中的定位--运输路线安排问题LRP研究评述[J].管理工程学报,2004(4):45-49.LIN Yan,HU Xiang-pei,WANG Xu-yin.Review on Location-Routing Problems (LRP) in Systematic Optimization of Logistics[J].Journal of Industrial Engineering/Engineering Management,2004(4):45-49.
[2]Wu Tai-His,Chinyao L,Bai Jiunn-Wei.Heuristic Solutions to Multi-depot Location-Routing Problems[J].Computer and Operation Research,2002,29:1393-1415.
[3]Jean Y,John J B,Loren K P.Heuristics Based on Space Filling Curves for Combinatorial Problems in Euclidean Space[J].Management Science,1988,34:291-305.
[4]Potvin J M R.An Exchange Heuristic for Routing Problems with Time Windows[J].Journal of Operational Research Society,1995,46:60-66.
[5]Robert L B,Paul H C.The Spacefilling Curves with Optimal Partitioning Heuristic for the Vehicle Routing Problem[J].European Journal of Operation Research,1994,76:128-142.
[6]张波,叶家玮,胡郁葱.模拟退火算法在路径优化问题中的应用[J].中国公路学报,2004,17(1):79-81.ZHANG Bo,YE Jia-wei,HU Yu-cong.Application of Optimizing the Path by Simulated Annealing[J].China Journal of Highway and Transport,2004,17(1):79-81.
[7]赵建有,闫旺,胡大伟.配送网络规划蚁群算法[J].交通运输工程学报,2004,4(3):79-81.ZHAO Jian-you,YAN Wang,HU Da-wei.Ant Colony Algorithm of Distribution Network Planning[J].Journal of Traffic and Transportation Engineering,2004,4(3):79-81.
[8]陈宽民,宋翔.基于动态规划理论的高速公路项目质量控制[J].长安大学学报:自然科学版,2005,25(1):51-55.CHEN Kuan-min,SONG Xiang.Quality Control of Freeway Item Based on Dynamic Programming Theory[J].Journal of Chang'an University:Natural Science Edition,2005,25(1):51-55.

收稿日期：2005年6月12日

出版日期：2006年5月31日

请看PDF全文