Multi-Unloading Packing Problem Model Research Based on MMAS

doi:10.3969/j.issn.1674-0696.2016.02.32

Abstract

Abstract: Aiming at the packing problems of container truck with multiple loading points, goods variety and multi-truck carriers, cargo loading and unloading sequence for different unloading locations was generated. Mathematical model was set up based on volume, weight and loading-unloading distance and the constraints to various packing types were defined. Firstly, a feasible solution generated as per packing rule and packing constraint served as initial solution by ant colony algorithm. Then, pheromone and selection probability formula was defined in accordance with characteristics of ants route seeking on goods to calculate the optimum solution within certain cycle numbers by max-min ant colony algorithm so as to achieve the goal of maximum loading utilization and maximum volume utilization of goods truck. Finally, the rationality and effectiveness of this method is justified by a practical case.

Key words: traffic engineering, multi-unloading point, vehicle loading, max-min ant colony algorithm

摘要： 针对多卸载点、多种货物、多车承运中的箱式货车装箱问题，为需要在不同地点卸货的货物生成货物装卸序列。建立了基于体积、重量和装卸距离的数学模型，定义了各类装箱约束条件，首先按照装箱规则和装箱约束生成一个可行解作为蚁群算法的初始解，再根据蚂蚁在货物上寻路的特点定义了信息素和选择概率公式，通过最大最小蚁群算法在一定的循环次数内求得最优解，从而达到最大化货车的装载利用率和体积利用率的目标。最后通过一个实例证明了该方法的合理性和有效性。

关键词: 交通工程, 多卸载点, 车辆装箱, 最大最小蚁群算法

CLC Number:

TIAN Ran, SUN Linfu, TANG Huijia, LI Binyong. Multi-Unloading Packing Problem Model Research Based on MMAS[J]. Journal of Chongqing Jiaotong University(Natural Science), 2016, 35(2): 156-162.

田冉,孙林夫,唐慧佳,李斌勇. 基于最大最小蚁群算法的多卸载点车载装箱模型研究[J]. 重庆交通大学学报（自然科学版）, 2016, 35(2): 156-162.

References

［1］ JOHNSON D S.计算机和难解性-NP完全性理论导论［M］.张立昂,译.北京:科学出版社,1990:124-125.
JOHNSON D S.Computer and Intractability-NP Complete Theory Introduction［M］.ZHANG Li’ang,Translate.Beijing:Science Press,1990:124-125.
［2］ DOWSLAND K A,DOWSLAND W B.Packing problems［J］.European Journal of Operational Reasearch,1992,56(1):2-14.
［3］ ORTMANN F G,NTENE N,VAN VUUREN J H.New and improved level heuristics for the rectangular strip packing and variable-sized bin-packing problems［J］.European Journal of Operational Research,2010,203(2):306-315.
［4］ CRAINIC T G,PERBOLI G,TADEI R.“TS2 PACK”:a two-level tabu search for the three-dimensional bin packing problem［J］.European Journal of Operational Research,2009,195(3):744-760.
［5］ LARA O D,LABRADOR M A.A multi-objective ant colony-based optimization algorithm for the bin packing problem with load balancing［C］// 2010 IEEE Congress on Evolutionary Computation (CEC).IEEE,2010:1-8.
［6］张德富,彭煜,朱文兴,等.求解三维装箱问题的混合模拟退火算法［J］.计算机学报,2009,32(11):2147-2156.
ZHANG Defu,PENG Yu,ZHU Wenxing,et al.A hybrid simulated annealing algorithm for the three-dimensional packing problem［J］.Chinese Journal of Computers,2009,32(11):2147-2156.
［7］ HUANG Wenqi,HE Kun.A caving degree approach for the single container loading problem［J］.European Journal of Operational research,2009,196(1):93-101.
［8］卫家骏.一种集装箱船配载问题改进算法探讨［J］.重庆交通大学学报（自然科学版）,2009,28(5):969-972.
WEI Jiajun,.A revised algorithm to solve container ships stowage problem［J］.Journal of Chongqing Jiaotong University(Natural Science),2009,28(5):969-972.
［9］连志刚,林蔚天,曹宇,等.基于类粒子群算法的集装箱装载模型优化研究［J］.重庆交通大学学报（自然科学版）,2014,33(2):126-130.
LIAN Zhigang,LIN Weitian,CAO Yu,et al.Similar particle swarm optimization algorithm for the optimization of container loading model［J］.Journal of Chongqing Jiaotong University(Natural Science),2014,33(2):126-130.
［10］曹玲芝.求解三维装箱问题的混合模拟退火算法研究［D］.广州:华南理工大学,2013:23-40.
CAO Lingzhi.Studies on Hybrid Simulated Annealing Algorithm for Three-dimensional Bin Packing Problems［D］.Guangzhou:South China University of Technology,2013:23-40.
［11］靳志宏,于波,侯丽晓.厢式货车配载与配送的联合优化［J］.交通运输工程学报,2010,10(3):95-100.
JIN Zhihong,YU Bo,HOU Lixiao.Integrated optimization on both vehicle filling and routing for van truck transportation［J］.Journal of Traffic and Transportation Engineering,2010,10(3):95-100.
［12］LAYEB A,BOUSSALIA S R.A novel greedy quantum inspired cuckoo search algorithm for variable sized bin packing problem［J］.International Journal of Mathematics in Operational Research,2014,6(6):732-751.
［13］DORIGO M,BIRATTARI M.Ant Colony Optimization Encyclopedia of Machine Learning［M］.U.S:Springer,2010:215-216.
［14］NING Xin,KA-CHI L,CHUN-KIT L M.Dynamic construction site layout planning using max-min ant system［J］.Automation in Construction,2010,19(1):55-65.

[1]	TANG Jiqiang1,2, ZHONG Xinwei2, LIU Jian1, LI Tianrui3. Short Term Forecast of Rail Transit Passenger Flow Based on Time Series Seasonal Classification Model [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(07): 31-38.
[2]	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.
[3]	DENG Tianmin1, ZHU Jie2, ZHU Kaijia1, QU Zhihua3. Driving Style Recognition Method Based on iForest and Bisecting K-means Combined Algorithm [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(06): 1-6.
[4]	XU Maozeng, ZHANG Li. Identification of Road Section Congestion Influence Based on Bijective Soft Decision Theory [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(06): 7-11.
[5]	WANG Tao1, XIE Sihong1, LI Wenhao1,2, LI Wenyong1. Short-Term Traffic Flow Adaptive Prediction Model Based on FFOS-ELM and PF [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(06): 21-27.
[6]	ZHANG Cheng1, WANG Chengyin1, CHEN Zhiwei2, ZHANG Zhengxiang3, ZHANG Zilei3. Mining Method of Key Nodes of Urban Road Network Based on Spatial-Flow Degree [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(06): 28-35.
[7]	WANG Yonggang, ZHANG Heng, PENG Zhipeng, ZHOU Wanqi. Analysis of Influencing Factors of Taxi Accidents Based on Structural Equation Model [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(06): 36-42.
[8]	ZHU Shunyin, LI Weiji, LIN Xiaoyuan, XIAO Wenbin, WANG Hong. Setting No Re-inspection Control Point for Tourist Vehicles in Characteristic Towns [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(06): 52-58.
[9]	PAN Binghong1,2, HU Wei1, REN Hui1, SHAN Huimin1. Truck Side-Slip Velocity Model in Curve Road Section Based on TruckSim Simulation [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(05): 38-45.
[10]	WU Wenjing, SUN Renchao, ZONG Fang, JIA Hongfei. Subjective Attitude Identification and Impact Analysis of Residents Low-Carbon Commuting Travel [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(05): 53-58.
[11]	LI Jun, DENG Yuxin. Cluster Analysis of Taxi Spatiotemporal Behavior Based on Non-negative Matrix Factorization [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(05): 59-65.
[12]	CHENG Wei1, LIU Xiang1, LEI Jianming2. Optimization of Cycle Length of Intersection Signal Based on RBF Neural Network Prediction [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(04): 13-18.
[13]	SHI Tianliang, WANG Wenguang. Information View and Particle Swarm Optimization Algorithm in Urban Traffic Congestion [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(04): 19-25.
[14]	HE Yulong1, 2, LIU Lei1,2, CHI Jiaxin1,2. Risk of Vehicle Lane Change Behavior on Highway [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(04): 26-33.
[15]	WANG Lu1, CHEN Xiaoxin2, LI Huaen1. Critical Speed of Vehicles Running Stably on Expressway in the Weather of Rain and Snow under Strong Wind [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(04): 34-40.