A post-improvement procedure for the mixed load school bus routing problem

This paper aims to develop a mixed load algorithm for the school bus routing problem (SBRP) and measure its effects on the number of required vehicles. SBRP seeks to find optimal routes for a fleet of vehicles, where each vehicle transports students from their homes and to their schools while satisfying various constraints. When mixed load is allowed, students of different schools can get on the same bus at the same time. Although many of real world SBRP allow mixed load, only a few studies have considered these cases. In this paper, we present a new mixed load improvement algorithm and compare it with the only existing algorithm from the literature. Benchmark problems are proposed to compare the performances of algorithms and to stimulate other researchers’ further study. The proposed algorithm outperforms the existing algorithm on the benchmark problem instances. It has also been successfully applied to some of real-world SBRP and could reduce the required number of vehicles compared with the current practice.     

A metaheuristic for the school bus routing problem with bus stop selection

Existing literature on routing of school buses has focused mainly on building intricate models that attempt to capture as many real-life constraints and objectives as possible. In contrast, the focus of this paper is on understanding the joint problem of bus route generation and bus stop selection – two important sub-problems – in its most basic form. To this end, this paper defines the school bus routing problem (SBRP) as a variant of the vehicle routing problem in which three simultaneous decisions have to be made: (1) determine the set of stops to visit, (2) determine for each student which stop (s)he should walk to, and (3) determine routes that lie along the chosen stops, so that the total traveled distance is minimized. An MIP model of this basic problem is developed.     

Solving school bus routing problems through integer programming

In this paper, an exact solution approach is described for solving a real-life school bus routing problem (SBRP) for transporting the students of an elementary school throughout central Ankara, Turkey. The problem is modelled as a capacitated and distance constrained open vehicle routing problem and an associated integer linear program is presented. The integer program borrows some well-known inequalities from the vehicle routing problem, which are also shown to be valid for the SBRP under consideration. The optimal solution of the problem is computed using the proposed formulation, resulting in a saving of up to 28.6% in total travelling cost as compared to the current implementation.     

A school bus scheduling problem

This paper introduces a school bus scheduling problem wherein trips for each school are given. A trip consists of a sequence of bus stops and their designated school. Each school has its fixed time window within which trips should be completed. A school bus can serve multiple trips for multiple schools. The school bus scheduling problem seeks to optimize bus schedules to serve all the given trips considering the school time windows. We first model the problem as a vehicle routing problem with time windows (VRPTW) by treating a trip as a virtual stop. Two assignment problem based exact approaches are then proposed for special cases and a heuristic algorithm is proposed for more general cases. Benchmark problems and computational experiments are presented. Computational experiments show the effectiveness of the proposed approaches.     

A heuristic algorithm for the free newspaper delivery problem

This paper addresses the problem of finding an effective distribution plan to deliver free newspapers from a production plant to subway, bus, or tram stations. The overall goal is to combine two factors: first, the free newspaper producing company wants to minimize the number of vehicle trips needed to distribute all newspapers produced at the production plant. Second, the company is interested in minimizing the time needed to consume all newspapers, i.e., the time needed to get all the newspapers taken by the final readers. The resulting routing problem combines aspects of the vehicle routing problem with time windows, the inventory routing problem, and additional constraints related to the production schedule. We propose a formulation and different heuristic approaches, as well as a hybrid method. Computational tests with real world data show that the hybrid method is the best in various problem settings.     

Project selection with discounted returns and multiple constraints

This paper considers the problem of selecting a subset of N projects subject to multiple resource constraints. The objective is to maximize the net present value of the total return, where the return from each project depends on its completion time and the previously implemented projects. It is observed that the optimal order (sequence) of projects does not depend on the particular subset of selected projects and hence the overall problem reduces to a multiconstraint nonlinear integer (0–1) problem. This problem can be solved optimally in pseudo-polynomial time using a dynamic programming method but the method is impractical except when the number of constraints, K, is very small. We therefore propose two heuristic methods which require O(N³K) and O(N⁴K) computations, respectively, and evaluate them computationally on 640 problems with up to 100 projects and up to 8 constraints. The results show that the best heuristic is on the average within 0.08% of the optimum for the single-constraint case and within 2.61% of the optimum for the multiconstraint case.     

On some methods for entropy maximization and matrix scaling

We describe and survey in this paper iterative algorithms for solving the discrete maximum entropy problem with linear equality constraints. This problem has applications e.g. in image reconstruction from projections, transportation planning, and matrix scaling. In particular we study local convergence and asymptotic rate of convergence as a function of the iteration parameter. For the trip distribution problem in transportation planning and the equivalent problem of scaling a positive matrix to achieve a priori given row and column sums, it is shown how the iteration parameters can be chosen in an optimal way. We also consider the related problem of finding a matrix X, diagonally similar to a given matrix, such that corresponding row and column norms in X are all equal. Reports of some numerical tests are given.     

On pursuit problems in controlled distributed systems

In the present paper, we study the problem of transferring a system from one state into another state in the presence of a player trying to prevent the occurrence of this transfer in the system. The system dynamics is described by partial differential equations whose right-hand sides contain the player controls in additive form. In a similar setting, the problem was solved in several papers, but it has not been considered for the case in which various constraints are imposed on the controls of the players. Here, in contrast to several other papers, we consider games in the entire scale of spaces H _r , r ≥ 0. We propose a new approach for completing the pursuit under various constraints on the player controls.     

New minimax algorithm

The purpose of this paper is to suggest a new, efficient algorithm for the minmax problem $$\mathop {min}\limits_x \mathop {max}\limits_i f_i (x), x \in \Re ^n , i = 1, \ldots ,m,$$ wheref _i ,i=1,...,m, are real-valued functions defined on ? ⁿ . The problem is transformed into an equivalent inequality-constrained minimization problem, mint, s.t.f _i (x)?t≤0, for alli, i=1,...,m. The algorithm has these features: an active-set strategy with three types of constraints; the use of slack variables to handle inequality constraints; and a trust-region strategy taking advantage of the structure of the problem. Following Tapia, this problem is solved by an active set strategy which uses three types of constraints (called here nonactive, semiactive, and active). Active constraints are treated as equality constraints, while semiactive constraints are treated as inequality constraints and are assigned slack variables. This strategy helps to prevent zigzagging. Numerical results are provided.     

Recent advances in vehicle routing exact algorithms

The capacitated vehicle routing problem (CVRP) is the problem in which a set of identical vehicles located at a central depot is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints. This paper provides a review of the most recent developments that had a major impact in the current state-of-the-art of exact algorithms for the CVRP. The most important mathematical formulations for the problem together with various CVRP relaxations are reviewed. The paper also describes the recent exact methods for the CVRP and reports a comparison of their computational performances.      

Minmax subtree cover problem on cacti

Let G=(V,E) be a connected graph such that edges and vertices are weighted by nonnegative reals. Let p be a positive integer. The minmax subtree cover problem (MSC) asks to find a pair (X,T) of a partition X={X₁,X₂,…,X_p} of V and a set T of p subtrees T₁,T₂,…,T_p, each T_i containing X_i so as to minimize the maximum cost of the subtrees, where the cost of T_i is defined to be the sum of the weights of edges in T_i and the weights of vertices in X_i. In this paper, we propose an O(p²n) time (4-4/(p+1))-approximation algorithm for the MSC when G is a cactus.     

Real-time vehicle rerouting problems with time windows

This paper introduces and studies real-time vehicle rerouting problems with time windows, applicable to delivery and/or pickup services that undergo service disruptions due to vehicle breakdowns. In such problems, one or more vehicles need to be rerouted, in real-time, to perform uninitiated services, with the objective to minimize a weighted sum of operating, service cancellation and route disruption costs. A Lagrangian relaxation based-heuristic is developed, which includes an insertion based-algorithm to obtain a feasible solution for the primal problem. A dynamic programming based algorithm solves heuristically the shortest path problems with resource constraints that result from the Lagrangian relaxation. Computational experiments show that the developed Lagrangian heuristic performs very well.     

Least squares problems with inequality constraints as quadratic constraints

Linear least squares problems with box constraints are commonly solved to find model parameters within bounds based on physical considerations. Common algorithms include Bounded Variable Least Squares (BVLS) and the Matlab function lsqlin. Here, the goal is to find solutions to ill-posed inverse problems that lie within box constraints. To do this, we formulate the box constraints as quadratic constraints, and solve the corresponding unconstrained regularized least squares problem. Using box constraints as quadratic constraints is an efficient approach because the optimization problem has a closed form solution. The effectiveness of the proposed algorithm is investigated through solving three benchmark problems and one from a hydrological application. Results are compared with solutions found by lsqlin, and the quadratically constrained formulation is solved using the L-curve, maximum a posteriori estimation (MAP), and the χ² regularization method. The χ² regularization method with quadratic constraints is the most effective method for solving least squares problems with box constraints.     

Multiplier rules and the separation of convex sets

We consider the following abstract mathematical programming problem: in a setD, find an element that optimizes a real function φ₀, subject to inequality constraints φ₁?0, ..., φ _p ?0 and equality constraints φ _p+1=0, ..., φ _p+q =0. Necessary conditions for this problem, like the Karush-Kuhn-Tucker theorem, can be seen as a consequence of separating with a hyperplane two convex sets inR ^p+q+1, the image space of the map Φ=(φ₀, φ₁, ..., φ _p+q ). This paper reviews this approach and organizes it into a coherent way of looking at necessary conditions in optimization theory.     

The explicit solution of the profit maximization problem with box-constrained inputs

In this paper we study the profit-maximization problem, considering maximum constraints for the general case of m-inputs and using the Cobb-Douglas model for the production function. To do so, we previously study the firm’s cost minimization problem, proposing an equivalent infimal convolution problem for exponential-type functions. This study provides an analytical expression of the production cost function, which is found to be a piece-wise potential. Moreover, we prove that this solution belongs to class C¹. Using this cost function, we obtain the explicit expression of maximum profit. Finally, we illustrate the results obtained in this paper with an example.     

Parallel machine scheduling with machine availability and eligibility constraints

In this paper we consider the problem of scheduling n independent jobs on m identical machines incorporating machine availability and eligibility constraints while minimizing the makespan. Each machine is not continuously available at all times and each job can only be processed on specified machines. A network flow approach is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time binary search algorithm to either verify the infeasibility of the problem or solve it optimally if a feasible schedule exists.     

Optimization of chance constraint programming with sum-of-fractional objectives – An application to assembled printed circuit board problem

This paper presents a procedure to solve a chance constraint programming problem with sum-of-fractional objectives. The problem and the solution procedure are described with the help of a practical problem – assembled printed circuit boards (PCBs). Errors occurring during assembling PCBs are in general classified into three kinds, viz. machine errors, manual errors and other errors. These errors may lead to the rejection of the major portion of the production and hence result the manufacturer a huge loss. The problem is decomposed to have two objective functions; one is a sum-of-fractional objectives and the other is a non-linear objective with bounded constraints. The interest is to maximize the sum-of-fractional objectives and to minimize the non-linear objective, subject to stochastic and non-stochastic bounded environment. The first problem deals with the maximization of the profit (maximizing sum-of-fractional objectives) and the second deals with the minimization of the loss (errors), so as to obtain the maximum profit after removing the number of defective PCBs.     

Finding K shortest looping paths with waiting time in a time–window network

A time-constrained shortest path problem is a shortest path problem including time constraints that are commonly modeled by the form of time windows. Finding K shortest paths are suitable for the problem associated with constraints that are difficult to define or optimize simultaneously. Depending on the types of constraints, these K paths are generally classified into either simple paths or looping paths. In the presence of time–window constraints, waiting time occurs but is largely ignored. Given a network with such constraints, the contribution of this paper is to develop a polynomial time algorithm that finds the first K shortest looping paths including waiting time. The time complexity of the algorithm is O(rK²|V₁|³), where r is the number of different windows of a node and |V₁| is the number of nodes in the original network.     

Solving balanced Procrustes problem with some constraints by eigenvalue decomposition

The balanced Procrustes problem with some special constraints such as symmetric orthogonality and symmetric idempotence are considered. By one time eigenvalue decomposition of the matrix product generated by the matrices A and B, the constrained solutions are constructed simply. Similar strategy is applied to the problem with the corresponding P-commuting constraints with a given symmetric matrix P. Numerical examples are presented to show the efficiency of the proposed methods.     

A network-consistent time-dependent travel time layer for routing optimization problems

In the vehicle routing literature, there is an increasing focus on time-dependent routing problems, where the time (or cost) to travel between any pair of nodes (customers, depots) depends on the departure time. The aim of such algorithms is to be able to take recurring congestion into account when planning logistics operations. To test algorithms for time-dependent routing problems, time-dependent problem data is necessary. This data usually comes in the form of three-dimensional travel time matrices that add the departure time as an extra dimension. However, most currently available time-dependent travel time matrices are not network-consistent, i.e., the travel times are not correlated both in time and in space. This stands in contrast to the behavior of real life congestion, which generally follows a specific pattern, appearing in specific areas and then affecting all travel times to and from those areas. As a result of the lack of available network-consistent travel time matrices, it is difficult to develop algorithms that are able to take this special structure of the travel time data into account.