Shipment planning at oil refineries using column generation and valid inequalities

In this paper we suggest an optimization model and a solution method for a shipment planning problem. This problem concerns the simultaneous planning of how to route a fleet of ships and the planning of which products to transport in these ships. The ships are used for moving products from oil refineries to storage depots. There are inventory levels to consider both at the refineries and at the depots. The inventory levels are affected by the process scheduling at the refineries and demand at the depots. The problem is formulated using an optimization model including an aggregated representation of the process scheduling at the refineries. Hence, we integrate the shipment planning and the process scheduling at the refineries. We suggest a solution method based on column generation, valid inequalities, and constraint branching. The solution method is tested on data provided by the Nynas oil refinery company and solutions are obtained within 4 hours, for problem instances of up to 3 refineries, 15 depots, and 4 products when considering a time horizon of 42 days.     

Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points

The problem of scheduling delivery vehicles from a number of depots to customers, subject to constraints on load and distance or time, is considered. A new algorithm is presented; this allows routes from several depots to be constructed simultaneously, subject to restrictions on numbers of vehicles at individual depots. Where too many customers require service, a flexible priority rule will select those to be served. Results for the single depot case are compared with other known algorithms; further results are given and discussed for cases of several depots.     

Multi-depot vehicle scheduling problems with time windows and waiting costs

The multi-depot vehicle scheduling problem with time windows (MDVSPTW) consists of scheduling a fleet of vehicles to cover a set of tasks at minimum cost. Each task is restricted to begin within a prescribed time interval and vehicles are supplied by different depots. The problem is formulated as an integer nonlinear multi-commodity network flow model with time variables and is solved using a column generation approach embedded in a branch-and-bound framework. This paper breaks new ground by considering costs on exact waiting times between two consecutive tasks instead of minimal waiting times. This new and more realistic cost structure gives rise to a nonlinear objective function in the model. Optimal and heuristic versions of the algorithm have been extensively tested on randomly generated urban bus scheduling problem (UBSP) and freight transport scheduling problem (FTSP). The results show that such a general solution methodology outperforms specialized algorithms when minimal waiting costs are used, and can efficiently treat the case with exact waiting costs.     

A truck scheduling problem arising in intermodal container transportation

We address a truck scheduling problem that arises in intermodal container transportation, where containers need to be transported between customers (shippers or receivers) and container terminals (rail or maritime) and vice versa. The transportation requests are handled by a trucking company which operates several depots and a fleet of homogeneous trucks that must be routed and scheduled to minimize the total truck operating time under hard time window constraints imposed by the customers and terminals. Empty containers are considered as transportation resources and are provided by the trucking company for freight transportation. The truck scheduling problem at hand is formulated as Full-Truckload Pickup and Delivery Problem with Time Windows (FTPDPTW) and is solved by a 2-stage heuristic solution approach. This solution method was specially designed for the truck scheduling problem but can be applied to other problems as well. We assess the quality of our solution approach on several computational experiments.     

A time–space network based exact optimization model for multi-depot bus scheduling

The vehicle scheduling problem, arising in public transport bus companies, addresses the task of assigning buses to cover a given set of timetabled trips with consideration of practical requirements, such as multiple depots and vehicle types as well as depot capacities. An optimal schedule is characterized by minimal fleet size and minimal operational costs including costs for unloaded trips and waiting time. This paper discusses the multi-depot, multi-vehicle-type bus scheduling problem (MDVSP), involving multiple depots for vehicles and different vehicle types for timetabled trips. We use time–space-based instead of connection-based networks for MDVSP modeling. This leads to a crucial size reduction of the corresponding mathematical models compared to well-known connection-based network flow or set partitioning models. The proposed modeling approach enables us to solve real-world problem instances with thousands of scheduled trips by direct application of standard optimization software. To our knowledge, the largest problems that we solved to optimality could not be solved by any existing exact approach. The presented research results have been developed in co-operation with the provider of transportation planning software PTV AG. A software component to support planners in public transport was designed and implemented in context of this co-operation as well.     

An adaptive search for the response time variability problem

The Response Time Variability Problem (RTVP) is an NP-hard combinatorial scheduling problem, which has recently been reported and formalised in the literature. This problem has a wide range of real-world applications in mixed-model assembly lines, multi-threaded computer systems, broadcast of commercial videotapes and others. The RTVP arises whenever products, clients or jobs need to be sequenced in such a way that the variability in the time between the points at which they receive the necessary resources is minimised. We propose a greedy but adaptive heuristic that avoids being trapped into a poor solution by incorporating a look ahead strategy suitable for this particular scheduling problem. The proposed heuristic outperforms the best existing methods, while being much faster and easier to understand and to implement.     

New facets for the two-stage uncapacitated facility location polytope

The two-stage uncapacitated facility location problem is considered. This problem involves a system providing a choice of depots and plants, each with an associated location cost, and a set of demand points which must be supplied, in such a way that the total cost is minimized. The formulations used until now to approach the problem were symmetric in plants and depots. In this paper the asymmetry inherent to the problem is taken into account to enforce the formulation which can be seen like a set packing problem and new facet defining inequalities for the convex hull of the feasible solutions are obtained. A computational study is carried out which illustrates the interest of the new facets. A new family of facets recently developed, termed lifted fans, is tested with success.     

On the collection depots location problem

In this paper we investigate the problem of locating a new facility servicing a set of demand points. A given set of collection depots is also given. When service is required by a demand point, the server travels from the facility to the demand point, then from the demand point to one of the collection depots (which provides the shortest route back to the facility), and back to the facility. The problem is analyzed and properties of the solution point are formulated and proved. Computational results on randomly generated problems are reported.     

Models for scheduling charges in continuous casting: application to a Brazilian steel plant

In this paper we propose models for the scheduling of charges considering the alternatives of intermix slabs or setups between consecutive jobs. The study is motivated by the practical need of a steel plant in Brazil to reduce costs in a low volumes/wide range of products environment. An intermix slab is formed when two jobs with different grades and/or widths are processed without stopping the machine. This may generate a poor material, which has low commercial value or is used as scrap. The machine may also be stopped between two consecutive jobs to allow a setup. The setup operation has an associated cost, but no intermix slab is created. Thus, the scheduling problem consists of defining the sequence of charges and whether an intermix slab or a setup operation must take place to minimize the total cost. We report computational experiments on real data. This study, by comparing results with actual schedules planned, shows that significant cost savings upon practice can be achieved by running the proposed models on standard optimization packages.     

Application of an optimization problem in Max-Plus algebra to scheduling problems

The problem tackled in this paper deals with products of a finite number of triangular matrices in Max-Plus algebra, and more precisely with an optimization problem related to the product order. We propose a polynomial time optimization algorithm for 2×2 matrices products. We show that the problem under consideration generalizes numerous scheduling problems, like single machine problems or two-machine flow shop problems. Then, we show that for 3×3 matrices, the problem is NP-hard and we propose a branch-and-bound algorithm, lower bounds and upper bounds to solve it. We show that an important number of results in the literature can be obtained by solving the presented problem, which is a generalization of single machine problems, two- and three-machine flow shop scheduling problems. The branch-and-bound algorithm is tested in the general case and for a particular case and some computational experiments are presented and discussed.     

Analysis,modeling and solution of the concrete delivery problem

This paper describes a specific local search approach to solve a problem arising in logistics which we prove to be NP-hard. The problem is a complex scheduling or vehicle routing problem where we have to schedule the tours of concrete mixer vehicles over a working day from concrete-producing depots to concrete-demanding customers and vice versa. We give a general mixed integer programming model which is too hard to solve for state of the art mixed integer programming optimizers in the case of the usually huge problem instances coming from practice. Therefore we present a certain local search approach to be able to handle huge practical problem instances.     

Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking

As shown in recent researches, the costs in distribution systems may be excessive if routes are ignored when locating depots. The location routing problem (LRP) overcomes this drawback by simultaneously tackling location and routing decisions. This paper presents a new metaheuristic to solve the LRP with capacitated routes and depots. A first phase executes a GRASP, based on an extended and randomized version of Clarke and Wright algorithm. This phase is implemented with a learning process on the choice of depots. In a second phase, new solutions are generated by a post-optimization using a path relinking. The method is evaluated on sets of randomly generated instances, and compared to other heuristics and a lower bound. Solutions are obtained in a reasonable amount of time for such a strategic problem. Furthermore, the algorithm is competitive with a metaheuristic published for the case of uncapacitated depots.     

Lower bounds for the two-stage uncapacitated facility location problem

In the two-stage uncapacitated facility location problem, a set of customers is served from a set of depots which receives the product from a set of plants. If a plant or depot serves a product, a fixed cost must be paid, and there are different transportation costs between plants and depots, and depots and customers. The objective is to locate plants and depots, given both sets of potential locations, such that each customer is served and the total cost is as minimal as possible. In this paper, we present a mixed integer formulation based on twice-indexed transportation variables, and perform an analysis of several Lagrangian relaxations which are obtained from it, trying to determine good lower bounds on its optimal value. Computational results are also presented which support the theoretical potential of one of the relaxations.     

Optimizing solid waste collection in Brussels

This paper reports on a project dealing with waste collection management. A methodology used in this case study combines an operations research method with systems engineering. It illustrates how waste transportation costs are minimized in a major urban area. Due to the complexity of a real size situation, a model is developed to consider a set of points for the collection routes rather than the arcs making up the streets. Several means of transportation including transportation by vehicle, rail and canal are evaluated. Collector vehicles reside overnight in depots and daily evacuate accumulated waste to an incinerator or a transfer station where it is deposited before being shipped out to the incinerator. The latter two sites are called terminal sites. Although optimization models are too difficult to solve with existing means, useful collection strategies are found to give some grounds to decisions made by urban administrators.     

Location of depots in a sugar-beet distribution system

In the following case study the problem of the location of depots in a sugar-beet distribution system for a certain sugar enterprise in Poland is considered. The sugar-beet is delivered from farms to sugar-mills either directly or through some depots. Lower and upper limits on the depot throughputs are imposed. The depot investment and operating costs are estimated by a piecewiselinear function. Given a set of possible depot locations, costs associated with the depots and the unit transportation costs, we seek a minimum cost location-transportation plan determining the number, location and sizes of the depots to be opened and the amounts of the sugar-beet flows. Two solution procedures are developed: (1) The application of MPSX and MIP systems for the problem of the reduced size; (2) The heuristic method. Based upon the computational results both approaches can be treated as alternative solution techniques to the presented problem.     

Optimizing dead mileage in urban bus routes through a nondominated solution approach

The problem of determining nondominated schedules to take buses from depots to the starting points of their routes, spare capacity and the number of buses to be parked overnight at each depot is considered with two objectives without assigning priorities to them. The two objectives are to minimize the cumulative distance covered by all the buses and the maximum distance among the distances covered by individual buses from the depots to the starting points of their respective routes. An algorithm is developed to obtain the set of nondominated solutions of this two-objective problem.     

Leakage detection and location in gas pipelines through an LPV identification approach

A new approach to gas leakage detection in high pressure distribution networks is proposed, where two leakage detectors are modelled as a linear parameter varying (LPV) system whose scheduling signals are, respectively, intake and offtake pressures. Running the two detectors simultaneously allows for leakage location. First, the pipeline is identified from operational data, supplied by REN-Gasodutos and using an LPV systems identification algorithm proposed in [1]. Each leakage detector uses two Kalman filters where the fault is viewed as an augmented state. The first filter estimates the flow using a calculated scheduling signal, assuming that there is no leakage. Therefore it works as a reference. The second one uses a measured scheduling signal and the augmented state is compared with the reference value. Whenever there is a significant difference, a leakage is detected. The effectiveness of this method is illustrated with an example where a mixture of real and simulated data is used.     

排序问题中优化准则关于基本参数的正则性及其应用

本文提出了优化准则关于加工时间、准备时间、应交工时间的正则性，利用这种正则性对寻找参数可控排序问题中的有效值、有效解给出了一直观算法，并指出对一些具体的参数可控排序问题，其有效值、有效解的寻找可通过对这一直观算法加以具体化而得．文中还对平均流程问题给出了这样一个具体化算法．     

Solving the response time variability problem by means of a genetic algorithm

The response time variability problem (RTVP) is a hard scheduling problem that has recently been defined in the literature and has a wide range of real-world applications in mixed-model assembly lines, multithreaded computer systems, network environments and others. The RTVP arises whenever products, clients or jobs need to be sequenced in such a way that the variability in the time between the points at which they receive the necessary resources is minimized. Since the RTVP is a complex problem, heuristic and metaheuristic techniques are needed to solve it. The best results in the literature for the RTVP have been obtained with a psychoclonal algorithm. We propose a genetic algorithm (GA) that is adapted to solve the RTVP. A computational experiment is carried out and it is shown that, on average, the GA produces better results than the psychoclonal algorithm.