摘要
研究包含时间窗、多车场因素的二维装箱车辆路径问题,建立相应的数学模型,并提出求解该问题的一种新的混合算法,混合算法由量子粒子群算法和引导式局部搜索算法组成。其中,量子粒子群算法用于求解车辆路径问题,引导式局部搜索算法用于求解可行装箱方案。在引导式局部搜索算法中,提出一种基于最小浪费原则的启发式装箱规则,以灵活确定待装货物和装货空间之间的匹配关系,减少重复确定装箱方案所消耗的时间。设计了两组数值试验:第一组基于标准算例库,并将混合算法计算结果与已有文献中的结果进行对比;第二组基于随机生成的新算例,新算例给出多车场和时间窗数据,用于演示混合算法对新模型的计算过程和计算结果。两组数值试验的结果表明,混合算法在效率和性能方面均有较好的表现,计算结果和计算时间均优于已有文献,且混合算法能够较好的求解包含时间窗、多车场因素的二维装箱车辆路径问题模型。
Both vehicle routing problem(VRP)and bin packing problem(BPP)are important,typical combinatorial optimization problems,and are frequently and independently studied in the past few decades.In recent years,some attention has been devoted to their combined optimization,called 2L-CVRP(two-dimensional capacitated vehicle routing problem),which is a combination of two important NP-hard optimization problems in distribution logistics.In the 2L-CVRP,clients demand are defined as sets of rectangular weighted items,while vehicles have a weight capacity and a rectangular two-dimensional loading surface.The objective of the 2L-CVPR is to serve all the customers and load the corresponding items into the vehicles,through a road network,with minimum total cost.Problem description:In this paper,a multi-depots capacitated vehicle routing problem with time window where client demand is composed of two-dimensional weighted items is addressed(2L-CVRP-MDTM).The model and an improved hybrid algorithm to solve the problem are proposed.The hybrid algorithm GLS-QPSO is composed by the Quantum-behaved Particle Swarm Optimization algorithm which is applied to solve the vehicle routing problem and Guided Local Search algorithm which is used to identify the feasible packing solutions.Method:New loading heuristic rules are proposed in Guided Local Search algorithm based on the principle of minimize the waste to get better results of the matching relationship between the items and the corresponding packing positions in shorter time.Through the algorithm we can get the tours,and identify the clients covered by the vehicles,as well as vehicles in the routes.All the items demanded by the clients need to be loaded in the vehicles with the related constrains.In fact,there are two aspects that packing algorithm needs to consider.One is to determine the next loading item,and another is to determine the feasible loading position.Computational experiments:Twenty of these 2L-CVRP standard instances are selected randomly,and loading surface(L,W)is fixed
出处
《中国管理科学》
CSSCI
CSCD
北大核心
2017年第7期67-77,共11页
Chinese Journal of Management Science
基金
国家自然科学基金青年项目(71602008)
北京市社会科学基金研究基地项目(16JDGLC032)
北京交通大学人才基金(B15RC00150)
关键词
车辆路径问题
二维装箱问题
量子粒子群算法
多车场
时间窗
vehicle routing problem
two-dimensional packing problem
Quantum-behaved Particle Swarm Optimization algorithm
multi-depots
time window
