需求可拆分车辆路径问题及其优化算法研究

Vehicle routing optimization is at the core of passenger and freight transportation management of all transportation modes, as well as physical distribution and logistics management, which is called as the vehicle routing problem (VRP). According to whether the customer's demand allows to be completed only by one vehicle or to be split between two or more vehicles, it is divided into VRP without split loads and VRP with split loads. Among the work for the VRP with split loads reported in the literature, those to quantify the benefit of using split loads for the VRP are comparatively more than those to focus on the optimization algorithm for each type of problem, and basically only the case in which the customer's demand is split by the measurement unit in goods delivery is considered. This project will mainly research on the cases of passenger transportation and splitting customer's demand by invoice (order) in goods delivery, and their main types of problem, such as the VRP with split loads and soft time windows, the split load open VRP (OVRP) with pickup and delivery, the split load OVRP with soft time windows and pickup and delivery, etc, aiming at proposing the solution models and algorithms by utilizing the theory and method of multiple programming and metaheuristic. The algorithms will be coded and tested by the benchmark problems. The expectant research achievement will provide new theory and method for the passenger and freight transportation management, as well as physical distribution and logistics management.

车辆路径优化是客货运输和物流配送管理中的核心问题之一，一般称之为车辆路径问题（VRP）。根据客户点的运输需求是只允许由一辆车完成，还是允许对其进行拆分由多辆车共同完成，可分为需求不可拆分和可拆分VRP。已有的针对需求可拆分VRP的研究工作中，论证需求可拆分情形在经济上的有利性的相对较多，而对求解各类型问题的优化算法的还相对较少，且基本上只考虑货物运输中客户点的需求按计量单位拆分的情形。本项目将主要对文献中尚少有涉及的货物以货票（订单）为单位进行需求拆分、以及旅客运输等应用背景及其主要问题类型，如带软时间窗的需求可拆分VRP、带取送作业的需求可拆分开放式VRP（OVRP）、带取送作业和软时间窗的需求可拆分OVRP等进行研究。运用多目标规划和智能优化算法的相关理论和方法，研究建立其求解模型和优化算法，并进行编程运算和测试分析。预期的研究成果将为物流配送和客货运输管理提供新的优化理论和方法。

车辆路径优化是客货运输和物流配送管理中的核心问题之一，一般称之为车辆路径问题（Vehicle Routing Problem, VRP），属NP-难问题，对其求解算法的研究是重点和难点。根据客户点的运输需求是只允许由一辆车完成，还是允许对其进行拆分由多辆车共同完成，可分为需求不可拆分和可拆分VRP。根据车辆完成任务后是否必须返回原出发点以及返回的形式，可分为闭合式VRP和开放式VRP（OVRP）两大类。本项目主要对文献中尚少有涉及的货物运输中需求以订单（货票）为单位进行离散拆分的需求可拆分VRP的主要问题类型及其优化算法开展研究，具体为：(1)需求依订单（可离散）拆分的VRP，(2)带软时间窗的需求依订单拆分的VRP，(3)带路长的依订单拆分VRP，(4)需求依订单拆分的OVRP等。与此同时，结合需求可拆分VRP研究的发展趋势和应用背景，对(1) 带碳排放约束（基于绿色物流）的VRP，(2)动态VRP，(3)选址-路径问题，(4)库存-路径问题，(5)铁路机车乘务交路优化编制问题，(6)客户点需求量需求预测等问题也开展了相应的拓展研究。运用多目标规划、智能优化算法等的相关理论和方法，分别研究建立了各类问题的数学模型和智能求解算法，并对所有算法进行了编程运算和测试分析。项目的研究成果为改进物流配送和交通运输管理中的车辆运输路线优化编制等相关工作提供了新的优化理论和方法。