带二维装箱约束的团队定向问题模型及优化算法

doi:10.3969/j.issn.1674-0696.2016.03.29

重庆交通大学学报（自然科学版） ›› 2016, Vol. 35 ›› Issue (3): 141-146.DOI: 10.3969/j.issn.1674-0696.2016.03.29

带二维装箱约束的团队定向问题模型及优化算法

彭勇，宋其勤

（重庆交通大学交通运输学院，重庆 400074）

收稿日期:2014-10-09 修回日期:2015-01-04 出版日期:2016-06-20 发布日期:2016-06-20
作者简介:第一作者：彭勇(1973—)，男，重庆人，教授，博士，主要从事交通运输规划与管理方面的研究。E-mail:pengyong@cqjtu.edu.cn。

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

PENG Yong, SONG Qiqin

（School of Traffic & Transportation, Chongqing Jiaotong University, Chongqing 400074, P.R.China）

Received:2014-10-09 Revised:2015-01-04 Online:2016-06-20 Published:2016-06-20

摘要/Abstract

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

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

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

中图分类号:

U492.3+1

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

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.

参考文献

［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]	李晶1,2，钟鹏1，吕靖1,2. 基于系统动力学的陆港与城市经济互动研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 1-7.
[2]	李军1，朱云升2. 三角模糊层次分析的综合评价在黄河库区船舶安全评估中的应用[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 16-22.
[3]	邓萍1,2，宋莲1，黄承锋1,2. 三峡坝区过闸船舶拥堵成本测算及对坝区货物总价值影响研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 23-30.
[4]	程谦1 ，朱晓宁2 ，卢万胜3. 中长运距城际旅客出行方式选择行为模型——以高铁、民航为例[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 39-45.
[5]	连齐才1，李涵1，石小林1，闫章存2. 基于面板数据Mixed logit模型的自动驾驶选择行为分析[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 46-52.
[6]	戚春华，王笑男，朱守林，李航天. 基于驾驶员视觉兴趣区域的交通工程设施信息量阈值研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 53-60.
[7]	李升朝，吴越，白雪萌，王玥，张海. 基于TOPSIS与灰色关联的危货车辆违规报警研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 61-66.
[8]	杨庆芳1,2,3，王立强2，郑黎黎1,2,3，孟凡运2. 一种环形交叉口交通排放及燃油消耗模型研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 67-73.
[9]	白翰，张康宇，王修光，燕翔，冯启龙. 合放交通流条件下城市交叉口通行能力研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(06): 12-20.
[10]	张重阳,黄淑萍. 路网抗震可靠性及震后运输调度路径选择研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(06): 43-51.
[11]	郭文文1，计明军2，祝慧灵3，周文杰2. 集装箱码头场桥调度优化模型研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(06): 66-72.
[12]	李广儒，张新，朱庆辉. 基于Adaboost的改进Elman神经网络港口吞吐量预测方法[J]. 重庆交通大学学报（自然科学版）, 2021, 40(05): 1-5.
[13]	孙元广1，茧敏2，金华2，陈绍宽2. 城市轨道交通列车故障救援延误计算与仿真[J]. 重庆交通大学学报（自然科学版）, 2021, 40(05): 6-12.
[14]	王宏刚1,2，白朋1，邹庆茹2，赵玲1. 地铁车辆段股道运用优化模型[J]. 重庆交通大学学报（自然科学版）, 2021, 40(05): 13-18.
[15]	孙延浩1,2，张琦1,2，任禹谋1,2,3，孙鹏举4. 高速铁路列车调度员应急处置能力评价研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(05): 19-25.

带二维装箱约束的团队定向问题模型及优化算法

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics