Model of Team Orienteering Problem with Two-Dimensional Loading Constraint and Its Optimization Algorithm

doi:10.3969/j.issn.1674-0696.2016.03.29

Abstract

Abstract: Taking the limited vehicle service resources, special goods loading requirements and other factors into account, a special logistic problem to maximize the profit — a team orienteering problem with two-dimensional loading constraint was studied. On the base of clear definition of the above problem, a corresponding mathematic model was established. Aiming at the model characteristics, a heuristic algorithm was designed, which took the genetic algorithm as a framework and made use of BLF algorithm to ensure two-dimensional loading constraint model. Numerical studies verify the effectiveness of the proposed algorithm.

Key words: traffic and transportation engineering, team orienteering problem, two-dimensional loading constraint, GA

摘要： 研究了在车辆服务资源有限、货物有特殊装载要求和其他因素影响下，为了能获得最大效益而采取特殊物流配送的问题——带二维装箱约束的团队定向问题。在对该问题进行明确定义基础上，建立了相应的数学模型；针对模型特点，设计了以遗传算法为框架，利用基于BLF的算法确保二维装箱约束的模型启发式算法。数值算例验证了算法的有效性。

关键词: 交通运输工程, 团队定向问题, 二维装箱约束, 遗传算法

CLC Number:

U492.3+1

PENG Yong, SONG Qiqin. Model of Team Orienteering Problem with Two-Dimensional Loading Constraint and Its Optimization Algorithm[J]. Journal of Chongqing Jiaotong University(Natural Science), 2016, 35(3): 141-146.

彭勇，宋其勤. 带二维装箱约束的团队定向问题模型及优化算法[J]. 重庆交通大学学报（自然科学版）, 2016, 35(3): 141-146.

References

［1］ CHAO I M, GOLDEN B L, WASIL E A. The team orienteering problem［J］. European Journal of Operational Research, 1996, 88(3): 464-474.
［2］ VANSTEENWEGEN P, SOURLAU W, OUDHEUSDEN D. The orienteering problem: a survey［J］. European Journal of Operational Research, 2011, 209(1): 1-10.
［3］彭勇,谢禄江,刘松.时变单车路径问题建模及算法设计［J］.重庆交通大学学报(自然科学版),2013,32(2):263-266.
PENG Yong, XIE Lujiang, LIU Song. Route modeling and algorithm designing of time-dependent single vehicle［J］. Journal of Chongqing Jiaotong University(Natural Science), 2013,32(2):263-266.
［4］彭勇,何俊生.实时路网单车多任务物流配送路径优化［J］.重庆交通大学学报(自然科学版),2014,33(2):123-125.
PENG Yong, HE Junsheng. Route optimization of multi-trip single vehicle based on real time road network［J］. Journal of Chongqing Jiaotong University(Natural Science), 2014,33(2):123-125.
［5］李毅,陆百川,刘春旭.车辆路径问题的混沌粒子群算法研究［J］. 重庆交通大学学报(自然科学版),2012,31(4):842-845.
LI Yi, LU Baichuan, LIU Chunxu. Research on chaos particleswarm optimization algorithm for vehicle routing problem［J］. Journal of Chongqing Jiaotong University(Natural Science),2012,31(4):842- 845.
［6］王征,胡祥培,王旭坪.带二维装箱约束的物流配送车辆路径问题［J］.系统工程理论与实践,2011,31(12):2328-2341.
WANG Zheng, HU Xiangpei, WANG Xuping. Vehicle routing problem in distribution with two-dimensional loading constraint ［J］. Systems Engineering Theory & Practice, 2011, 31(12): 2328-2341.
［7］ BAKER B S, COFFMAN J E G, RIVEST R L. Orthogonal packing in two dimensions［J］.SIAM Journal on Computing,1980,9(4): 846-855.
［8］ BROWN D J. An improved BL lower bound［J］.Information Processing Letters,1980,11(1):37-39.
［9］武晓今,朱仲英.二维装箱问题的一种实现方法［J］.微型电脑应用,2003,19(4):20-23.
WU Xiaojin, ZHU Zhongying. A method to solve two-dimensional loading problem［J］. Microcomputer Applications,2003,19(4):20-23.
［10］ DANG Duc-cuong, GUIBADJ R N, Moukrim A. A PSO-based memetic algorithm for the team orienteering problem［J］. Applications of Evolutionary Computation,2008,4974:649-658.
［11］ BOULY H, DANG Duc-cuong, MOUKRIM A. A memetic algorithm for the team orienteering problem［J］.Applications of Evolutionary Computation,2008,4974:49-70.
［12］ DANG D C, GUIBADJ R N, MOUKRIM A. An effective PSO-inspired algorithm for the team orienteering problem［J］. European Journal of Operational Research,2013,229(2):332-344
［13］ KIM B I, LI Hong, ANDREW L J. An augmented large neighborhood search method for solving the team orienreering problem［J］. Expert Systems with Applications,2013,40(8):3065- 3072
［14］ BEAN J C. Genetic algorithms and random keys for sequencing and optimization［J］. ORSA Journal on Computing,1994,6(2):154-160.

[1]	LI Jing1,2, ZHONG Peng1, LYU Jing1,2. Interaction between Land Port and Urban Economy Based on System Dynamics [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(07): 1-7.
[2]	LI Jun1, ZHU Yunsheng2. Application of Comprehensive Evaluation of Triangular Fuzzy Analytic Hierarchy Process in Ship Safety Assessment of the Yellow River Reservoir Area [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(07): 16-22.
[3]	DENG Ping1,2, SONG Lian1, HUANG Chengfeng1,2. Estimation of Congestion Costs for Lockage Ship in Three Gorges Dam Area and Its Impact on the Total Value of Goods in the Dam Area [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(07): 23-30.
[4]	CHENG Qian1, ZHU Xiaoning2, LU Wansheng3. Travel Mode Choice Behavior Model of Intercity Passengers with Medium and Long Haul — A Case Study of High-Speed Railway and Air Transport [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(07): 39-45.
[5]	LIAN Qicai1, LI Han1, SHI Xiaolin1, YAN Zhangcun2. Autonomous Driving Choice Behavior Based on Panel Data Mixed Logit Model [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(07): 46-52.
[6]	QI Chunhua, WANG Xiaonan, ZHU Shoulin, LI Hangtian. Traffic Engineering Facility Information Threshold Based on Drivers Visual Area of Interest [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(07): 53-60.
[7]	LI Shengchao, WU Yue, BAI Xuemeng, WANG Yue, ZHANG Hai. Violation Alarm of Dangerous Goods Vehicle Based on TOPSIS and Gray Correlation [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(07): 61-66.
[8]	YANG Qingfang1,2,3, WANG Liqiang2, ZHENG Lili1,2,3, MENG Fanyun2. Traffic Emission and Fuel Consumption Model of Roundabout [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(07): 67-73.
[9]	ZHANG Dongdong, ZONG Zichun, FENG Jinzhi. Multi-objective Optimization of Shift Law for Two-Gear AMT Based on NSGA-Ⅱ Algorithm [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(07): 128-135.
[10]	BAI Han, ZHANG Kangyu, WANG Xiuguang, YAN Xiang, FENG Qilong. Traffic Capacity of Urban Intersection under the Conditions of Mixed Release of Traffic Flow [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(06): 12-20.
[11]	ZHANG Chongyang, HUANG Shuping. Seismic Reliability of Road Network and Route Selection of Post-Earthquake Transportation [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(06): 43-51.
[12]	GUO Wenwen1, JI Mingjun2, ZHU Huiling3, ZHOU Wenjie2. Optimization Model of Yard Crane Scheduling in a Container Terminal [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(06): 66-72.
[13]	LI Guangru, ZHANG Xin, ZHU Qinghui. Prediction Method of Port Throughput with Improved Elman Neural Network Based on Adaboost [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(05): 1-5.
[14]	SUN Yuanguang1, JIAN Min2, JIN Hua2, CHEN Shaokuan2. Calculation and Simulation of Delay during Train Failure Rescue of Urban Rail Transit [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(05): 6-12.
[15]	WANG Honggang1,2, BAI Peng1, ZOU Qingru2, ZHAO Ling1. Optimization Model of Track Application for Metro Depots [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(05): 13-18.