Abstract: Due to the convenience of the “door-to-door” service provided by trucks, full truckload transportation services, such as container truck transportation, have become quite common. Faced with fluctuating demand, transportation companies typically maintain a small fleet of their own vehicles on a regular basis and outsource some orders during peak demand periods to reduce costs. However, outsourcing can lead to a loss of control over transportation organization and service quality. Consequently, when deciding to outsource orders, transportation companies often consider certain very important orders that should not be outsourced. The decision-making problem for full truckload transportation restricting some orders to be outsourced requires solving a full truckload pickup and delivery routing problem with order selection restriction (FTPDRP-OSR), which is complex. Existing models and algorithms find it challenging to directly address this problem.
To overcome the above research gap, this paper establishes an arc-based mixed integer linear programming model and a set-partitioning binary programming model for the FTPDRP-OSR, respectively. The properties of the binary programming model are analyzed, reducing the number of decision variables. Since the problem at hand is an extension of the multiple travelling salesman problem, which is a NP hard problem, by directly using a mixed integer programming solver, it will be difficult to obtain satisfactory solutions within a given time period when the order scale is large. Therefore, a column-generation-based labeling dynamic programming algorithm and a branch-and-price algorithm are designed. In both algorithms, solutions generated by a time-window partitioning approximation algorithm serve as initial solutions; labels and dominance rules are customized for the order selection restriction; the branching strategy in the branch-and-price algorithm adopts the most infeasible branching strategy, prioritizing variables with fractional parts closest to 0.5 for branching.
To verify the effectiveness of the proposed model and algorithms, numerical experiments are designed for randomly generated instances. The results of the numerical experiments indicate that the branch-and-price algorithm can obtain exact solutions for small-scale instances, albeit taking more time than directly solving with a mixed integer programming solver (CPLEX). However, in large-scale instances, the column-generation-based label dynamic programming algorithm performs better than directly solving with CPLEX. Within an hour ofsolving time for large-scale instances, the gap between the upper and lower bounds for the former is 0.02%, compared to 6.48% for the latter, and the average optimal solution obtained by the former reduces by 1.46% compared to the best solution obtained by the latter.
This paper addresses the single-depot scenario of the FTPDRP-OSR. In reality, many transportation companies operate with multiple depots. Considering the FTPDRP-OSR with multiple depots more closely reflects real-world scenarios and has greater practical significance. However, when considering the multi-depot FTPDRP-OSR, the problem scale and the dimension of decision variables increase significantly, making the solution more challenging. In the future, the proposed algorithms will be extended to the multi-depot scenario of FTPDRP-OSR. By employing a decomposition strategy, the multi-depot scenario can be transformed into multiple single-depot scenarios for solving. Moreover, in practice, transportation and service times of trucks often exhibit randomness, while this paper only considers deterministic cases. Exploring the FTPDRP-OSR with stochastic times presents another research direction.

Key words: vehicle routing problem, truckload pickup and delivery, order selection, time-window-partition based-approximation algorithm, column generation

摘要： 带订单选择限制的整车取送货路径问题是卡车运输外包决策中一类重要问题。由于订单外包限制约束, 使得求解整车取送货路径问题的高精度解比较困难。为解决该问题, 本文分别建立了带订单选择限制的整车取送货路径问题的基于弧的混合整数规划模型和集划分模型, 设计了基于列生成的标签算法和分支定价精确求解算法。在两种算法中,采用时间窗划分近似算法获得较好的初始解;针对订单选择限制约束定制了标签和支配规则;分支定价算法采用最不可行分支策略,即优先选择小数部分最接近0.5的变量进行分支。数值实验表明, 分支定价算法能够求得小规模算例的最优解,但是所用时间大于混合整数规划求解器(CPLEX)直接求解。相比求解器直接求解,基于列生成的标签算法在求解较大规模算例时表现更优,能求得近似最优解;在一小时的求解时间限制下,前者能够求得的上下界的差距为0.02%, 后者的上下界的差距为6.48%。

关键词: 车辆路径问题, 整车取送货, 订单选择, 时间窗分割近似算法, 列生成