A column generation approach for a school bus routing problem with resource constraints

The Multiple Vehicle Traveling Purchaser Problem describes a school bus routing problem that combines bus stop selection and bus route generation. This problem aims at selecting a set of bus stops from among a group of potential locations to pick up students, and for designing bus routes to visit the selected stops and to carry the students to their school. We address a variation of this problem that considers certain constraints on each bus route, such as bounds on the distances traveled by the students, bounds on the number of visited bus stops, and bounds on the minimum number of students that a vehicle has to pick up.     

The traveling purchaser problem,with multiple stacks and deliveries: A branch-and-cut approach

The Double Traveling Salesman Problem with Multiple Stacks is a pickup-and-delivery single-vehicle routing problem which performs all pickup operations before the deliveries. The vehicle has a loading space divided into stacks of a fixed height that follows a Last-In-First-Out policy. It has to collect products following a Hamiltonian tour in a pickup region, and then deliver them following a Hamiltonian tour in a delivery region. The aim is to minimize the total routing cost while satisfying the vehicle loading constraints.     

Exact algorithms for the double vehicle routing problem with multiple stacks

The Double Traveling Salesman Problem with Multiple Stacks (DTSPMS) is a one-to-one pickup-and-delivery single-vehicle routing problem with backhaul deliveries. The vehicle carries a container divided into stacks of fixed height, each following a Last-In-First-Out policy, and the aim is to perform pickups and deliveries by minimizing the total routing cost and ensuring a feasible loading/unloading of the vehicle.A realistic generalization of the DTSPMS arises when a single vehicle is not enough to collect all products, and therefore multiple, and possibly heterogeneous vehicles are needed to perform the transportation operations. This paper introduces and formulates this generalization, that we refer as the Double Vehicle Routing Problem with Multiple Stacks. It proposes three models, the first one based on a three-index formulation and solved by a branch-and-cut algorithm, and the other two based on two set partitioning formulations using different families of columns and solved by a branch-and-price and a branch-and-price-and-cut algorithm, respectively.The performance of these algorithms has been studied on a wide family of benchmark test instances, observing that, although the branch-and-cut algorithm shows a better performance on instances with a small number of vehicles, the performance of the branch-and-price and the branch-and-price-and-cut algorithms improves as the number of vehicles grows. Additionally, the first set partitioning formulation yields tighter lower bounds, but the second formulation, because of its simplicity, provides better convergence properties, solving instances with up to fifty vertices to proven optimality.     

A bi-level school bus routing problem with bus stops selection and possibility of demand outsourcing

This paper develops a bi-level mathematical model for the school bus routing problem aiming at designing an efficient transportation system considering the possibility of predicting the students’ response. In the real world, the demand for using private cars depends on how well public transportation systems are operating especially in metropolitan cities. An inefficient public transportation will lead to an increase in the demand for using private cars. This issue will result in problems such as increased traffics and urban pollutions. To address this issue, an efficient public transportation system is designed by developing a new bi-level mathematical model. In the proposed model, the designer of the public transportation system, as the upper-level decision-maker, will locate appropriate bus stops and identify bus navigation routes. Subsequently, the decision regarding the allocation of students to transportation systems or outsourcing them will be made at the lower level which is considered as an operational-level decision-making. To solve this problem, two hybrid metaheuristic approaches named GA-EX-TS and SA-EX-TS have been proposed based on location-allocation-routing (LAR) strategy. The performance of these proposed methods is compared with exact solutions achieved from an explicit enumeration approach followed in the small-scale instances. Finally, the proposed approaches are used to solve 50 random instance problems. Comparing the results of the two tuned hybrid algorithms and conducting the sensitivity analysis of the model provide evidence for the good performance of the proposed approach.     

Heuristic and exact algorithms for a min–max selective vehicle routing problem

In this work, we investigate a vehicle routing problem where not all clients need to be visited and the goal is to minimize the longest vehicle route. We propose two exact solution approaches for solving the problem: a Branch-and-cut (BC) algorithm and a Local Branching (LB) method that uses BC as its inner solver. Our computational experience indicates that, in practice, the problem is difficult to solve, mainly when the number of vehicles grows. In addition to the exact methods, we present a heuristic that relies on GRASP and on the resolution of a restricted integer program based on a set covering reformulation for the problem. The heuristic was capable of significantly improving the best solutions provided by BC and LB, in one tenth of the times taken by them to achieve their best upper bounds.     

校车路径问题的改进迭代局部搜索算法

针对考虑站点服务时间、学生最大乘车时间约束的校车路径问题(SBRP),提出一种改进迭代局部搜索(ILS)算法以提升求解质量。该算法使用大规模邻域搜索(LNS)算法作为扰动算子;在解的破坏过程中,设计一组解的破坏因子并赋以一定的选择概率,每隔若干次迭代后根据解的质量自适应更改破坏因子的选择概率,进而调整解的破坏程度。为提升ILS解的多样性,算法采用了基于偏差系数的邻域解接受准则。在国际基准测试案例上进行了测试,测试结果表明在ILS算法中使用自适应调整破坏程度的LNS扰动比常规扰动和其他破坏扰动的求解质量有大幅提升;与蚁群算法的比较结果进一步验证了改进算法的有效性。     

A column generation approach to the heterogeneous fleet vehicle routing problem

We consider a vehicle routing problem with a heterogeneous fleet of vehicles having various capacities, fixed costs and variable costs. An approach based on column generation (CG) is applied for its solution, hitherto successful only in the vehicle routing problem with time windows. A tight integer programming model is presented, the linear programming relaxation of which is solved by the CG technique. A couple of dynamic programming schemes developed for the classical vehicle routing problem are emulated with some modifications to efficiently generate feasible columns. With the tight lower bounds thereby obtained, the branch-and-bound procedure is activated to obtain an integer solution. Computational experience with the benchmark test instances confirms that our approach outperforms all the existing algorithms both in terms of the quality of solutions generated and the solution time.     

The green vehicle routing problem: A heuristic based exact solution approach

This paper develops a simulated annealing heuristic based exact solution approach to solve the green vehicle routing problem (G-VRP) which extends the classical vehicle routing problem by considering a limited driving range of vehicles in conjunction with limited refueling infrastructure. The problem particularly arises for companies and agencies that employ a fleet of alternative energy powered vehicles on transportation systems for urban areas or for goods distribution. Exact algorithm is based on the branch-and-cut algorithm which combines several valid inequalities derived from the literature to improve lower bounds and introduces a heuristic algorithm based on simulated annealing to obtain upper bounds. Solution approach is evaluated in terms of the number of test instances solved to optimality, bound quality and computation time to reach the best solution of the various test problems. Computational results show that 22 of 40 instances with 20 customers can be solved optimally within reasonable computation time.     

A two-phase metaheuristic for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem, which aims to minimize the total arrival time at customers, is a relatively new variant of vehicle routing problem. It can be used to model many real-world applications, e.g., the important application arisen from the humanitarian aid after a natural disaster. In this paper, an approach, called two-phase metaheuristic, is proposed to deal with this problem. This algorithm starts from a solution. At each iteration, two interdependent phases use different perturbation and local search operators for solution improvement. The effectiveness of the proposed algorithm is empirically investigated. The comparison results show that the proposed algorithm is promising. Moreover, for nine benchmark instances, the two-phase metaheuristic can find better solutions than those reported in the previous literature.     

The memetic self-organizing map approach to the vehicle routing problem

The paper presents an extension of the self- organizing map (SOM) by embedding it into an evolutionary algorithm to solve the Vehicle Routing Problem (VRP). We call it the memetic SOM. The approach is based on the standard SOM algorithm used as a main operator in a population based search. This operator is combined with other derived operators specifically dedicated for greedy insertion moves, a fitness evaluation and a selection operator. The main operators have a similar structure based on the closest point findings and local moves performed in the plane. They can be interpreted as performing parallels and massive insertions, simulating the behavior of agents which interact continuously, having localized and limited abilities. This self-organizing process is intended to allow adaptation to noisy data as well as to confer robustness according to demand fluctuation. Selection is intended to guide the population based search toward useful solution compromises. We show that the approach performs better, with respect to solution quality and/or computation time, than other neural network applications to the VRP presented in the literature. As well, it substantially reduces the gap to classical Operations Research heuristics, specifically on the large VRP instances with time duration constraint.     

A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows

The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known and complex combinatorial problem, which has received considerable attention in recent years. This problem has been addressed using many different techniques including both exact and heuristic methods. The VRPTW benchmark problems of Solomon [Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research 1987; 35(2): 254–65] have been most commonly chosen to evaluate and compare all algorithms. Results from exact methods have been improved considerably because of parallel implementations and modern branch-and-cut techniques. However, 24 out of the 56 high order instances from Solomon's original test set still remain unsolved. Additionally, in many cases a prohibitive time is needed to find the exact solution. Many of the heuristic methods developed have proved to be efficient in identifying good solutions in reasonable amounts of time. Unfortunately, whilst the research efforts based on exact methods have been focused on the total travel distance, the focus of almost all heuristic attempts has been on the number of vehicles. Consequently, it is more difficult to compare and take advantage of the strong points from each approach. This paper proposes a robust heuristic approach for the VRPTW using travel distance as the main objective through an efficient genetic algorithm and a set partitioning formulation. The tests were produced using real numbers and truncated data type, allowing a direct comparison of its results against previously published heuristic and exact methods. Furthermore, computational results show that the proposed heuristic approach outperforms all previously known and published heuristic methods in terms of the minimal travel distance.     

公司班车的协同车辆路径问题

考虑员工上下班时间及早晚高峰期影响班车行驶速度等因素,建立协同车辆路径问题的数学模型.针对蚁群优化算法的缺点,结合具有快速全局搜索能力的遗传算法,并自适应地改变信息素挥发因子,采用混沌搜索产生初始种群可以加速染色体向最优解收敛,平滑机制有助于对搜索空间进行更有效的搜索,构成混合自适应蚁群优化算法.应用该算法和蚁群优化算法对该模型求解,实验证明了构造算法在收敛速度和寻优结果两方面都优于蚁群优化算法.     

校车路径问题的约束检测算法

依据校车服务学校的数量和顺序可将校车路径问题（SBRP）分为单校、多校不混载和多校混载三类。现有算法对不同类型的SBRP进行容量、时间窗等约束检测时采用不同的方法,对待复杂应用需要通过遍历进行检测。为此设计一种适用于不同类型SBRP的分段检测算法,将路径上的学校站点视为检测点,按检测点对路径分段,基于各个检测路段上的剩余容量和剩余时间检测整条路径是否违反约束。最后在大规模混载校车路径问题上的实验表明分段检测算法是有效的。     

Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm

E-commerce and logistics companies are facing important challenges to satisfy the rapid growth of customer demands. Unmanned aerial vehicles such as drones are an emerging technology that are very useful to cope with rising customer expectations of fast, flexible, and reliable delivery services. Drones work in tandem with trucks to perform parcel delivery, which have proven to reduce costs, CO2 emissions, and delivery times. This research proposes a mixed integer programming formulation to address the Vehicle Routing Problem with Drone (VRPD) by assigning customers to drone-truck pairs, determining the number of dispatching drone-truck units, and obtaining optimal service routes while the fixed and travel costs of both vehicles are minimized. Given the NP-hard nature of the VRPD, an ant colony optimization (ACO) algorithm is elaborated to solve this problem. Two novel methods are proposed to investigate the efficiency of the drone-truck combination by allowing the drones to perform additional delivery services to only one feasible customer and also multiple feasible customers while the truck waits at a customer location. Experimental results show that the proposed ACO algorithm can effectively solve the VRDP for different size instances and different customer location distributions, and is successful in providing timely solutions for small test instances within 1% of the optimal solutions. Finally, experimentation also reveals that the ACO algorithm outperforms the classical VRP by obtaining cost-savings of over 30% for large instances.     

A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem

In the heterogeneous fleet vehicle routing problem (HVRP), several different types of vehicles can be used to service the customers. The types of vehicles differ with respect to capacity, fixed cost, and variable cost. We assume that the number of vehicles of each type is fixed and equal to a constant. We must decide how to make the best use of the fixed fleet of heterogeneous vehicles.     

A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet

Nowadays genetic algorithms stand as a trend to solve NP-complete and NP-hard problems. In this paper, we present a new hybrid metaheuristic which uses parallel genetic algorithms and scatter search coupled with a decomposition-into-petals procedure for solving a class of vehicle routing and scheduling problems. The parallel genetic algorithm presented is based on the island model and its performance is evaluated for a heterogeneous fleet problem, which is considered a problem much harder to solve than the homogeneous vehicle routing problem.     

Packing first,routing second—a heuristic for the vehicle routing and loading problem

The Vehicle Routing and Loading Problem (VRLP) results by combining vehicle routing, possibly with time windows, and three-dimensional loading. Some packing constraints of high practical relevance, among them an unloading sequence constraint and a support constraint, are also part of the VRLP. Different formulations of the VRLP are considered and the issue is discussed under which circumstances routing and packing should be tackled as a combined task. A two-stage heuristic is presented following a “packing first, routing second” approach, i.e. the packing of goods and the routing of vehicles is done in two strictly separated stages. High quality results are achieved in short computation times for the 46 VRLP instances recently introduced by Moura and Oliveira. Moreover 120 new large benchmark instances including up to 1000 customers and 50,000 boxes are introduced and results for these instances are also reported.     

The vehicle routing problem with multiple prioritized time windows: A case study

This paper addresses Multi-objective Vehicle Routing Problem with Multiple Prioritized Time Windows (VRPMPTW) in which the distributer proposes a set of all non-overlapping time windows with equal or different lengths and the customers prioritize these delivery time windows. VRPMPTW aims to find a set of routes of minimal total traveling cost and maximal customer satisfaction (with regard to the prioritized time windows), starting and ending at the depot, in such a way that each customer is visited by one vehicle given the capacity of the vehicle to satisfy a specific demand. This problem is inspired from a real life application. The contribution of this paper lies in its addressing the VRPMPTW from a problem definition, modeling and methodological point of view. We developed a mathematical model for this problem. This model can simply be used for a wide range of applications where the customers have multiple flexible time windows and violation of time windows may drop the satisfaction levels of customers and lead to profit loss in the long term. A Cooperative Coevolutionary Multi-objective Quantum-Genetic Algorithm (CCMQGA) is also proposed to solve this problem. A new local search is designed and used in CCMQGA to reach an appropriate pareto front. Finally, the proposed approach is employed in a real case study and the results of the proposed CCMQGA are compared with the current solution obtained from managerial experience, the results of NSGA-II and the multi-objective quantum-inspired evolutionary algorithm.     

Exact and heuristic algorithms for the vehicle routing problem with multiple interdependent time windows

In this paper a model and several solution procedures for a novel type of vehicle routing problems where time windows for the pickup of perishable goods depend on the dispatching policy used in the solution process are presented. This problem is referred to as Vehicle Routing Problem with multiple interdependent time windows (VRPmiTW) and is motivated by a project carried out with the Austrian Red Cross blood program to assist their logistics department. Several variants of a heuristic constructive procedure as well as a branch-and-bound based algorithm for this problem were developed and implemented. Besides finding the expected reduction in costs when compared with the current procedures of the Austrian Red Cross, the results show that the heuristic algorithms find solutions reasonably close to the optimum in fractions of a second. Another important finding is that increasing the number of pickups at selected customers beyond the theoretical minimum number of pickups yields significantly greater potential for cost reductions.     

A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows

This paper presents a new hybrid variable neighborhood-tabu search heuristic for the Vehicle Routing Problem with Multiple Time windows. It also proposes a minimum backward time slack algorithm applicable to a multiple time windows environment. This algorithm records the minimum waiting time and the minimum delay during route generation and adjusts the arrival and departure times backward. The implementation of the proposed heuristic is compared to an ant colony heuristic on benchmark instances involving multiple time windows. Computational results on newly generated instances are provided.