带装箱约束的开放多车辆调度问题的模型与算法研究

项目名称： 带装箱约束的开放多车辆调度问题的模型与算法研究

项目编号： No.61272003

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 自动化技术、计算机技术

项目作者： 张德富

作者单位： 厦门大学

项目金额： 60万元

中文摘要： 本项目考虑物流运输领域出现的带装箱约束的开放多车辆调度问题，该问题是一个新问题，组合了两个NP难问题（装箱问题和多车辆调度问题），因此它也是NP难问题，求解它实际上更难更具挑战性。本项目首先对该问题进行数学建模，给出灵活的目标函数。将基于评分规则的启发式算法进行扩展，提出求解多车辆装箱问题的启发式算法。接着在现有算法的基础上，设计出求解带装箱约束的开放多车辆调度问题的超启发式算法。基于算法参数的不同设置或不同超启发式算法，提出基于MapReduce的并行模型。最终设计出带装箱约束的开放多车辆调度问题的高效并行超启发式求解算法。其中邻域的构造、不同邻域的搜索方式以及算法复杂性也是深入研究的内容。本项目的研究成果可以为计算机、数学、运筹学、管理科学与工程等学科领域解决类似NP难问题提供新的优化方法，同时对减少车辆尾气排放、降低能源消耗、节省物流运输成本具有重要的现实意义。

中文关键词： 开放多车辆调度问题；MapReduce 并行模型；超启发式算法；组合优化；

英文摘要： We consider open multi-vehicle routing problems with loading constraints arising in logistics and transportation fields. These problems are new and combine two NP-hard problems(packing and multi-vehicle routing), therefore,they are NP-hard problems, and are more challenging and more difficult to be solved in practice. We first construct a flexible objective function for them,and then extend the packing heuristic based on scoring rules to solve multi-vehicle packing problems. Then we develop excellent metaheuristic algorithms for the considered problems. MapReduce parallel model is presented by different parameter settings or different metaheuristics. At last, we present parallel metaheuristic algorithms with high performance for the considered problems. Where,the construction of neighborhood,the search way of variable neighborhood and the analysis of the algorithm complexity are further investigated. Our research results provide new methods for solving other similar NP-Hard problems arising in computer,mathematics,operational research, management science and engineering fields, and have significant practice value for decreasing the CO2 emission,reducing the energy consumption, and saving the logistic cost.

英文关键词： Open multi-vichicle routing problem；Mapreduce Parallel model；Meta-heuristics；Combinatorial Optimization；