A Column Generation Approach to Delivery Planning over Time with Inhomogeneous Service Providers and Service Interval Constraints

We consider a problem of delivery planning over multiple time periods. Deliveries must be made to customers having nominated demand in each time period. Demand must be met in each time period by use of some combination of inhomogeneous service providers. Each service provider has a different delivery capacity, different cost of delivery to each customer, a different utilisation requirement, and different rules governing the spread of deliveries in time. The problem is to plan deliveries so as to minimise overall costs, subject to demand being met and service rules obeyed. A natural integer programming model was found to be intractable, except on problems with loose demand constraints, with gaps between best lower bound and best feasible solution of up to 35.1%, with an average of 15.4% over the test data set. In all but the problem with loosest demand constraints, Cplex 6.5 applied to this formulation failed to find the optimal solution before running out of memory. However a column generation approach improved the lower bound by between 0.6% and 21.9%, with an average of 9.9%, and in all cases found the optimal solution at the root node, without requiring branching.     

Solving a manpower scheduling problem for airline catering using metaheuristics

We study a manpower scheduling problem with job time windows and job-skills compatibility constraints. This problem is motivated by airline catering operations, whereby airline meals and other supplies are delivered to aircrafts on the tarmac just before the flights take-off. Jobs (flights) must be serviced within a given time-window by a team consisting of a driver and loader. Each driver/loader has the skills to service some, but not all, of the airline/aircraft/configuration of the jobs. Given the jobs to be serviced and the roster of workers for each shift, the problem is to form teams and assign teams and start-times for the jobs, so as to service as many flights as possible. Only teams with the appropriate skills can be assigned to a flight. Workload balance among the teams is also a consideration. We present model formulations and investigate a tabu search heuristic and a simulated annealing heuristic approach to solve the problem. Computational experiments show that the tabu search approach outperforms the simulated annealing approach, and is capable of finding good solutions.     

Generalizations of two identities of Guo and Yang

In this paper, we provide generalizations of two identities of Guo and Yang [2] for the q-binomial coe?cients. This approach allows us to derive new convolution identities for the complete and elementary symmetric functions. New identities involving q-binomial coe?cients are obtained as very special cases of these results. A new relationship between restricted partitions and restricted partitions into parts of two kinds is derived in this context.     

A simulated annealing heuristic for the team orienteering problem with time windows

This paper presents a simulated annealing based heuristic approach for the team orienteering problem with time windows (TOPTW). Given a set of known locations, each with a score, a service time, and a time window, the TOPTW finds a set of vehicle tours that maximizes the total collected scores. Each tour is limited in length and a visit to a location must start within the location’s service time window. The proposed heuristic is applied to benchmark instances. Computational results indicate that the proposed heuristic is competitive with other solution approaches in the literature.     

Vehicle routing in the 1-skip collection problem

In this paper, we consider a real problem, which we call the 1-skip collection problem, where a fleet of vehicles must collect a number of skips situated in different locations and transport them to one among different plants chosen on the basis of the kind of waste contained in the skip. Each vehicle has a capacity of one skip and it starts and ends its tour at the depot. Each time a vehicle collects a skip, it has to go to a plant and empty it. A number of constraints are imposed, which involve time windows for the customers and the plants, shift-time, different kinds of skips, number of drivers available to carry out the service and priorities assigned to the customers who have to be served. The objective is to minimize the total cost of the service given by the fixed cost of the drivers engaged to carry out the service, the cost of the extra time and the penalty cost paid if a customer is not served. A heuristic algorithm to solve the real problem is presented. The algorithm first constructs a feasible solution by means of the nearest-neighbour algorithm. Then, if it finds a feasible solution, it improves it. The computational results show that the solution of the algorithm is much better than the solution applied by the firm that carries out the service since it serves a higher number of skips with a smaller number of drivers.     

Some Problems Associated with the Distribution of Consumer Products

The distribution problem is considered as a whole. The interconnexions are shown between various subproblems: factory siting, warehouse (or depot) siting, subdepot siting, allocation of production resources to factory sites and minimization of costs. It is suggested that the results obtained for certain products distributed nationally through grocery outlets are valid (with qualifications) for any nationally marketed consumer product. The use of traditional operational research techniques, where appropriate, is referred to but not in great detail. A logical approach to siting problems, particularly the siting of a large number of subdepots, is outlined. The aim of this approach is to obtain the correct answers with the minimum amount of work. The implications for marketing are discussed with particular reference to costs: the cost of distributing goods to certain areas may be unduly high; the cost of customer service may rise disproportionately as the level of service given rises. A balance must be struck which is in line with the company's aims but which may mean modifying production, distribution and sales objectives.     

Multiprocessor scheduling under precedence constraints: Polyhedral results

We consider the problem of scheduling a set of tasks related by precedence constraints to a set of processors, so as to minimize their makespan. Each task has to be assigned to a unique processor and no preemption is allowed. A new integer programming formulation of the problem is given and strong valid inequalities are derived. A subset of the inequalities in this formulation has a strong combinatorial structure, which we use to define the polytope of partitions into linear orders. The facial structure of this polytope is investigated and facet defining inequalities are presented which may be helpful to tighten the integer programming formulation of other variants of multiprocessor scheduling problems. Numerical results on real-life problems are presented.     

Hybridized evolutionary local search algorithm for the team orienteering problem with time windows

The orienteering problem (OP) consists in finding an elementary path over a subset of vertices. Each vertex is associated with a profit that is collected on the visitor’s first visit. The objective is to maximize the collected profit with respect to a limit on the path’s length. The team orienteering problem (TOP) is an extension of the OP where a fixed number m of paths must be determined. This paper presents an effective hybrid metaheuristic to solve both the OP and the TOP with time windows. The method combines the greedy randomized adaptive search procedure (GRASP) with the evolutionary local search (ELS). ELS generates multiple distinct child solutions using a mutation mechanism. Each child solution is further improved by a local search procedure. GRASP provides multiple starting solutions to the ELS. The method is able to improve several best known results on available benchmark instances.     

A repeated matching heuristic for the single-source capacitated facility location problem

Facility location models form an important class of integer programming problems, with application in many areas such as the distribution and transportation industries. An important class of solution methods for these problems are so-called Lagrangean heuristics which have been shown to produce high quality solutions and which are at the same time robust. The general facility location problem can be divided into a number of special problems depending on the properties assumed. In the capacitated location problem each facility has a specific capacity on the service it provides. We describe a new solution approach for the capacitated facility location problem when each customer is served by a single facility. The approach is based on a repeated matching algorithm which essentially solves a series of matching problems until certain convergence criteria are satisfied. The method generates feasible solutions in each iteration in contrast to Lagrangean heuristics where problem dependent heuristics must be used to construct a feasible solution. Numerical results show that the approach produces solutions which are of similar and often better than those produced using the best Lagrangean heuristics.     

Pickup and delivery network segmentation using contiguous geographic clustering

This paper addresses the problem of partitioning a local service region into nonoverlapping work areas in which pickups and deliveries are made throughout the day. For a fleet of homogeneous vehicles, a given set of customers, and expected demand for service, the objective is to find the least number of work areas or clusters that satisfy a variety of geometric and capacity constraints. Using rectangles as the basic shape, each cluster must have an aspect ratio that falls within certain bounds, as well as meet load and time requirements dictated by the capacity of a vehicle and the working hours in a day, respectively. The latter requirement presents a unique hurdle because travel times are a function of the actual routes followed by the drivers, and are not known, even in a probabilistic sense, until the clusters are formed. A novel aspect of the paper is the method proposed for dealing with this uncertainty. The problem is modelled using a compact set-covering formulation and is solved with an adaptive column generation heuristic. Because it is not possible to efficiently represent all the constraints in algebraic form, thus allowing a Dantzig-Wolfe decomposition, a constructive approach was taken. The first step involved generating a subset of attractive clusters from seed customers scattered throughout the service region and then iteratively pricing them out to obtain a relaxed solution to the set-covering model. To find integer solutions, a three-phase variable fixing scheme was designed with the aim of balancing solution quality with runtimes. The full methodology was tested on six data sets provided by an internationally known express package carrier. The results showed that vehicle reductions averaging 7.6% could be realized by adopting the configurations derived from the proposed approach.     

Ordering the structural set of jobs,minimizing the total penalty

The problem of setting up a schedule minimizing the total penalty is solved. A job set is specified. There are no precedence conditions. Each job consists of elementary operations. Job interruptions are allowed. Interruptions of elementary operations are not allowed. The penalty for an operation of a job to be executed at instantt is. A schedule is evaluated by a penalty that is the sum of the penalties of all the elementary operations of all jobs in set. It is assumed that set is structural. The problem is to find the schedule with a start in a prescribed interval [ T₁,T₂] with the least penalty. Compatible structural schedules are introduced into consideration. The class of compatible structural schedules contains the solution of the problem. An algorithm solving the problem is proposed having complexity, in the worst case, whereK is the number of jobs in the set.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 90, pp. 229–264, 1979.     

The capacitated maximal covering location problem with backup service

The maximal covering location problem has been shown to be a useful tool in siting emergency services. In this paper we expand the model along two dimensions — workload capacities on facilities and the allocation of multiple levels of backup or prioritized service for all demand points. In emergency service facility location decisions such as ambulance sitting, when all of a facility's resources are needed to meet each call for service and the demand cannot be queued, the need for a backup unit may be required. This need is especially significant in areas of high demand. These areas also will often result in excessive workload for some facilities. Effective siting decisions, therefore, must address both the need for a backup response facility for each demand point and a reasonable limit on each facility's workload. In this paper, we develop a model which captures these concerns as well as present an efficient solution procedure using Lagrangian relaxation. Results of extensive computational experiments are presented to demonstrate the viability of the approach.     

An iterative three-component heuristic for the team orienteering problem with time windows

This paper studies the team orienteering problem with time windows, the aim of which is to maximize the total profit collected by visiting a set of customers with a limited number of vehicles. Each customer has a profit, a service time and a time window. A service provided to any customer must begin in his or her time window. We propose an iterative framework incorporating three components to solve this problem. The first two components are a local search procedure and a simulated annealing procedure. They explore the solution space and discover a set of routes. The third component recombines the routes to identify high quality solutions. Our computational results indicate that this heuristic outperforms the existing approaches in the literature in average performance by at least 0.41%. In addition, 35 new best solutions are found.     

Workforce routing and scheduling for electricity network maintenance with downtime minimization

We investigate a combined routing and scheduling problem for the maintenance of electricity networks. In electricity networks power lines must be regularly maintained to ensure a high quality of service. For safety reasons a power line must be physically disconnected from the network before maintenance work can be performed. After completing maintenance work the power line must be reconnected. Each maintenance job therefore consists of multiple tasks which must be performed at different locations in the network. The goal is to assign each task to a worker and to determine a schedule such that the downtimes of power lines and the travel effort of workers are minimized. For solving this problem, we combine a Large Neighborhood Search meta-heuristic with mathematical programming techniques. The method is evaluated on a large set of test instances which are derived from network data of a German electricity provider.     

Polyhedral study of the capacitated vehicle routing problem

The capacitated vehicle routing problem (CVRP) considered in this paper occurs when goods must be delivered from a central depot to clients with known demands, usingk vehicles of fixed capacity. Each client must be assigned to exactly one of the vehicles. The set of clients assigned to each vehicle must satisfy the capacity constraint. The goal is to minimize the total distance traveled. When the capacity of the vehicles is large enough, this problem reduces to the famous traveling salesman problem (TSP). A variant of the problem in which each client is visited by at least one vehicle, called the graphical vehicle routing problem (GVRP), is also considered in this paper and used as a relaxation of CVRP. Our approach for CVRP and GVRP is to extend the polyhedral results known for TSP. For example, the subtour elimination constraints can be generalized to facets of both CVRP and GVRP. Interesting classes of facets arise as a generalization of the comb inequalities, depending on whether the depot is in a handle, a tooth, both or neither. We report on the optimal solution of two problem instances by a cutting plane algorithm that only uses inequalities from the above classes.This work was supported in part by NSF grant DDM-8901495.     

An application of the minimal spanning tree approach to the cluster stability problem

Among the areas of data and text mining which are employed today in OR, science, economy and technology, clustering theory serves as a preprocessing step in the data analyzing. An important component of clustering theory is determination of the true number of clusters. This problem has not been satisfactorily solved. In our paper, this problem is addressed by the cluster stability approach. For several possible numbers of clusters, we estimate the stability of the partitions obtained from clustering of samples. Partitions are considered consistent if their clusters are stable. Clusters validity is measured by the total number of edges, in the clusters’ minimal spanning trees, connecting points from different samples. Actually, we use the Friedman and Rafsky two sample test statistic. The homogeneity hypothesis of well mingled samples, within the clusters, leads to an asymptotic normal distribution of the considered statistic. Resting upon this fact, the standard score of the mentioned edges quantity is set, and the partition quality is represented by the worst cluster, corresponding to the minimal standard score value. It is natural to expect that the true number of clusters can be characterized by the empirical distribution having the shortest left tail. The proposed methodology sequentially creates the described distribution and estimates its left-asymmetry. Several presented numerical experiments demonstrate the ability of the approach to detect the true number of clusters.     

A simple load balancing problem with decentralized information

The following load balancing problem is investigated in discrete time: A service system consists of two service stations and two controllers, one in front of each station. The service stations provide the same service with identical service time distributions and identical waiting costs. Customers requiring service arrive at a controller's site and are routed to one of the two stations by the controller. The processes describing the two arrival streams are identical. Each controller has perfect knowledge of the workload in its own station and receives information about the other station's workload with one unit of delay. The controllers' routing strategies that minimize the customers' total flowtime are determined for a certain range of the parameters that describe the arrival process and the service distribution. Specifically, we prove that optimal routing strategies are characterized by thresholds that are either precisely specified or take one of two possible values.     

Localizing combinatorial properties of partitions

The purpose of this paper is to develop a framework for the analysis of combinatorial properties of partitions. Our focus is on the relation between global properties of partitions and their localization to subpartitions. First, we study properties that are characterized by their local behavior. Second, we determine sufficient conditions for classes of partitions to have a member that has a given property. These conditions entail the possibility of being able to move from an arbitrary partition in the class to one that satisfies the given property by sequentially satisfying local variants of the property. We apply our approach to several properties of partitions that include consecutiveness, nestedness, order-consecutiveness, full nestedness and balancedness, and we demonstrate its usefulness in determining the existence of optimal partitions that satisfy such properties.     

Sylvester–Gallai Theorems for Complex Numbers and Quaternions

A Sylvester-Gallai (SG) configuration is a finite set S of points such that the line through any two points in S contains a third point of S. According to the Sylvester-Gallai theorem, an SG configuration in real projective space must be collinear. A problem of Serre (1966) asks whether an SG configuration in a complex projective space must be coplanar. This was proved by Kelly (1986) using a deep inequality of Hirzebruch. We give an elementary proof of this result, and then extend it to show that an SG configuration in projective space over the quaternions must be contained in a three-dimensional flat.     

A column generation approach for an emission-oriented vehicle routing problem on a multigraph

In this work, an emission-minimizing vehicle routing problem with heterogeneous vehicles and a heterogeneous road and traffic network is considered as it is typical in urban areas. Depending on the load of the vehicle, there exist multiple emission-minimal arcs for traveling between two locations. To solve the vehicle routing problem efficiently, a column generation approach is presented. At the core of the procedure an emission-oriented elementary shortest path problem on a multigraph is solved by a backward labeling algorithm. It is shown that the labeling algorithm can be sped up by adjusting the dual master program and by restricting the number of labels propagated in the sub-problem. The column generation technique is used to setup a fast heuristic as well as a branch-and-price algorithm. Both procedures are evaluated based on test instances with up to 100 customers. It turns out that the heuristic approach is very effective and generates near-optimal solutions with gaps below 0.1% on average while only requiring a fraction of the runtime of the exact approach.