面向物流行业的车辆路径问题研究与系统实现

Aiming at the logistics application, this project considers vehicle routing problems (VRP) and focuses on the mathematical modeling, algorithm design and system implementation. Firstly, based on the graph model and mathematical programming model for traditional VRP, some new constraints are considered aiming at logistics environment and a new VRP model is given. Secondly, several specific properties of the new VRP model are studied and the lower bound algorithms are designed. By combining the lower bound and convex hull, the polynomial-time approximation algorithms for the new VRP model will be considered. Finally, based on the new VRP model and the approximation algorithms, a vehicle routing software named GPARP will be implemented. Unlike the traditional VRP model, our VRP model considers some logistics-oriented constraints based on GRP model；comparing to the optimal algorithms and those heuristic algorithms, our approximation algorithms have both of their advantages and avoid their disadvantages, i.e., promise both time efficiency and result precision；contrary to the existing vehicle routing software, our GPARP applies logistics-oriented model and approximation algorithms, and involves the graphic interface. Hence, it has better performance and user interaction.

本项目面向物流行业应用实际，重点研究广义车辆路径问题，提出从数学建模、算法设计到系统实现的完整解决方案。首先，在广义路径问题的图论和数学规划模型的基础上，引入新的约束条件，建立更加符合实际应用的车辆路径模型；然后，研究新模型的具体性质，设计最优解下界算法，将最优解下界和凸包求解引入近似技术，设计可以求解新模型的多项式时间近似算法；最后，将理论成果应用于软件系统，开发出具有实际应用价值的车辆路径软件系统。 相比于传统的数学模型，本项目在GRP模型基础上引入适合物流行业的实际约束条件；相比于精确算法和启发式算法，本项目提出的近似算法可以同时保证时间高效性和结果准确性；相比于其他车辆路径软件系统，本项目拟开发的GPARP系统面向物流应用，在近似算法理论成果的基础上采用图形界面，具有更好的易用性。

本项目面向物流行业应用实际，研究了自适应两阶段和多阶段车辆路径问题、带时间窗的车辆路径问题、带距离和其他约束的车辆路径问题、冷链物流路径规划等问题，针对每一个具体的问题，建立相应的数学模型，设计有效的算法，并开发了车辆路径系统的原型。.相比于传统的数学模型，本项目在数学规划模型基础上引入适合物流行业的实际约束条件；除了设计精确算法和启发式算法，本项目重点研究了近似算法的设计，近似算法可以同时保证时间高效性和结果准确性；相比于其他车辆路径软件系统，本项目开发的系统面向物流应用，在近似算法理论成果的基础上采用百度地图作为界面，具有更好的易用性。