关键词: 序定约束, 车辆路径问题, 启发式算法, 分支定界法

Abstract: The problem proposed in the paper is motivated by automobile aftersales logistics, which particularly addresses a so-called sequence-definite routine which is a new operational pattern of transportation vehicle routine optimization from the consolidation centers to dealers. In the problem, a relative fixed time window is always assigned with each dealer because a relative fixed time window can reduce the waiting time, and increase the efficiencies of unloading in accord. In addition, the demands of volumes and weights for dealers, and the capacity of volumes and weights for trucks are generally considered. This paper formally defines the new concept of sequence-definite vehicle routine, where a series of no-intersection dealer sets are given to represent all dealers in a whole routine, each dealer set has its fixed routine sequence of dealers, and any feasible subroutine can only contain dealers as a subset of a given dealer set. Moreover, the routine sequence of dealers for a subroutine will follow the routine sequence of the given dealer set that contains dealers of the subroutine. The objective is to minimize the total transportation routine cost in the constraints of time windows of dealers, and volumes and weights of trucks. The paper has three contributes as follows. The first contribution is to simplify and propose a new theoretical problem of sequence defined vehicle routine problem with a new well theoretical defined concept of sequence defined vehicle routine. The second is to present a new fundamental vehicle routine mixed integer linear programming model with sequence-definite pattern and to prove its NP-hardness by a reduction from the partition problem. The third is to develop some basic properties of the sequence-definite routine problem and design efficient approximation and exact algorithms followed by comprehensive computational experiments. The studies have practical significance because the proposed new vehicle routine optimization problem exactly meets the practical pattern and the corresponding models and algorithms can be applied in automobile aftersales logistics decisions directly.
The computational intractability theory is used to show the hardness of our problem. We use the mixed integer linear programming method to model our new problem. The algorithm design and analysis methods including heuristics and branch and bound are applied to design efficient algorithms. Case studies are also given to show the efficiencies of our models and algorithms in practice.
Motivated by real practices, the paper successfully finds and formulates an interesting new vehicle routine optimization problem occurring in automobile aftersales logistics. The new concept of sequence-definite routine is introduced and a new optimization problem with sequence-definite is initially proposed. Our problem is shown to be NP-hard. Heuristic algorithms based on the bin packing characteristics and routine saving properties such as sequence-definite NF, sequence-definite BF, sequence-definite FF, sequence-definite saving algorithm and sequence-definite insertion are constructed. The branch-and-bound algorithm with efficient lower and upper bounds are further developed to solve the problem exactly. Furthermore, comprehensive numerical experiments show the effectiveness of our model and the efficiencies of proposed algorithms, and the sensitivity analysis are given as well. The branch and bound algorithms and the heuristic algorithms can achieve 27.53% and 17.93% cost savings, respectively. The case studies based on real data of an automobile after-sales spare parts logistics enterprises including three whole routines with 8, 10, 15 dealers respectively are conducted. Case studies show that the outputs of our model and algorithms can exactly meet the real decision requirements.
The concept of sequence definite routine is of theoretical significance not only in problem formulation, model building and algorithm design but also in providing a potential tool for algorithm design particularly for vehicle routine problem. Therefore, the future studies can be conducted by the following directions. One is to apply other advanced methodologies to study the sequence-definite vehicle routine problem of itself including machine learning, column generation, and Lagrange relaxation, in the hope of deriving more efficient mathematical models and algorithms. The other interesting direction is to develop a new search strategy in which a neighborhood of a local solution can be constructed as a set of visiting nodes with sequence definite routine, then the local search is performed on the neighborhood, and finally constructed iterative algorithms can be derived.
The paper is supported by the National Science Foundation of China (No.72172091). The authors thank Anji Zhixing Logistics for supports for investigations.

Key words: sequence definite constraint, vehicle routing problem, heuristic algorithm, branch and bound algorithm