Abstract This article introduces the cumulative school bus routing problem, which concerns the transport of students from a school using a fleet of identical buses. The objective of the problem is to select a drop‐off point for each student among potential locations within a certain walking distance and to generate routes such that the sum of arrival times of all students from their school to their homes is minimized. The article describes six polynomial‐size mixed integer linear programming formulations based on original and auxiliary graphs, and the formulations are numerically compared on real instances. The article reports the results of computational experiments performed to evaluate the performance of the proposed models.

In this paper we propose a new polynomially sized formulation of the well known symmetric capacitated vehicle routing problem . Formulations of polynomial size have already been published in the academic literature for this problem, but they all possess the feature that they contain many equivalent solutions. As such, the optimal set of routes will be represented by several equivalent integer feasible solutions to the formulation, potentially leading to excessive computation times. The equivalence between solutions results from the possibility of reversing the order of visit on any route, starting and ending at the depot, without affecting feasibility or route length. In contrast, the formulation proposed in this paper eliminates the existence of equivalent integer solutions . In particular, instead of describing a route as a path starting and ending at the depot, we represent a route as two paths originating from the depot and ending at a so called peak customer on the route. Moreover, in our formulation there is only one possible peak customer for any such two paths, resulting in a unique representation of any route. Our formulation has shown very competitive computing times compared to a classical formulation of comparable size. Consequently, our formulation can be recommended in combination with the use of algebraic modeling languages for entering a formulation in its entirety into a mixed-integer linear programming solver.

In this paper, we consider the Mixed Capacitated General Routing Problem which is a combination of the Capacitated Vehicle Routing Problem and the Capacitated Arc Routing Problem. The problem is also known as the Node, Edge, and Arc Routing Problem. We propose a Branch‐and‐Cut‐and‐Price algorithm for obtaining optimal solutions to the problem and present computational results based on a set of standard benchmark instances. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(3), 161–184 2016

This article is concerned with the problem of finding optimal vehicle routes to minimize the overall travel time, with constraints on the minimum and maximum amount of time spent on each route. The problem extends previous work on the distance‐constrained vehicle routing problem by introducing lower bounds on route durations to ensure that the resulting routes are balanced. The article also explicitly addresses the situation where a solution is artificially balanced as a result of inoptimal orders of visits. The article describes alternative ways in which the restrictions on route connectivity, duration, and artificial balancing can be formulated, and introduces an exact algorithm based on cutting planes and mixed‐integer linear programming. To the best of our knowledge, this is the first exact algorithm proposed for such a problem that explicitly addresses artificially balanced routes. Computational results are presented for three versions of the exact algorithm using TSPLIB instances. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(2), 166–179 2015