A new MIP model for mine equipment scheduling by minimizing maintenance cost

Mining investment has been recognized as capital intensive due mainly to the cost of large equipment. Equipment capital costs for a given operation are usually within the order of hundreds of million dollars but may reach to billion dollars for large companies operating multiple mines. Such large investments require the optimum usage of equipment in a manner that the operating costs are minimized and the utilization of equipment is maximized through optimal scheduling. This optimum usage is required to ensure that the business remains sustainable and financially stable. Most mining operations utilize trucks to haul the mined material. Maintenance is one of the major operating cost items for these fleets as it can reach approximately one hundred million dollars yearly. There is no method or application in the literature that optimizes the utilization for truck fleet over the life of mine. A new approach based on mixed integer programming (MIP) techniques is used for annually scheduling a fixed fleet of mining trucks in a given operation, over a multi-year time horizon to minimize maintenance cost. The model uses the truck age (total hours of usage), maintenance cost and required operating hours to achieve annual production targets to produce an optimum truck schedule. While this paper focuses on scheduling trucks for mining operation, concept can be used in most businesses using equipment with significant maintenance costs. A case study for a large scale gold mine showed an annual discounted (10% rate) maintenance cost saving of over $2M and more than 16% ($21M) of overall maintenance cost reduction over 10 years of mine life, compared with the spreadsheet based approach used currently at the operation.     

Improving fleet utilization for carriers by interval scheduling

Carriers are under increasing pressure to offset rising fuel charges with cost cutting or revenue generating schemes. One opportunity for cost reduction lies in asset management. This paper presents resource allocation scheduling models that can be used to assign truck loads to delivery times and trucks when delivery times are flexible. The paper makes two main contributions. First, we formulate the problem as a multi-objective optimization model — minimizing the number of trucks needed as well as the costs associated with tardiness or earliness — and demonstrate how improvements in fleet usage translate into savings which carriers can use as incentives to promote flexible delivery times for customers. Second, we show that a two-phase model with a polynomial algorithm in the second phase is able to produce optimal schedules in a reasonable time.     

考虑车辆限速区间的危险品运输网络优化

由于危险品在运输过程中存在极大的危害性,为了降低危险品运输风险,政府可以通过对不同路段设置不同的限速区间来引导危险品运输车辆的路径选择,从而导致不同的运输网络总风险和鲁棒成本。首先基于车辆限速区间的方法,构建了危险品运输网络优化的双层规划模型,上层规划以最大运输网络总风险值最小化为目标,下层规划以危险品运输企业的鲁棒成本最小化为目标;然后,设计了粒子群优化算法求解了该模型;最后,通过两个算例验证了模型和算法的有效性。计算结果表明政府部门运用车辆限速区间的方法不仅能够非常有效地降低危险品运输网络总风险,而且更具有鲁棒性和现实可操作性。     

Balancing fleet size and repositioning costs in LTL trucking

This paper develops an optimization modeling approach for analyzing the trade-off between the cost of a larger fleet of tractors and the cost of repositioning tractors for a trucking company operating a consolidation network, such as a less-than-truckload (LTL) company. Specifically, we analyze the value of using extra tractor repositioning moves (in addition to the ones required to balance resources throughout the network) to reduce the fixed costs of owning or leasing a tractor fleet during a planning horizon. We develop network flow optimization models, some with side constraints and nonlinear objective functions, using event-based, time-expanded networks to determine appropriate fleet sizes and extra repositioning moves under different repositioning strategies, and we compare the optimal costs of the strategies. For repositioning costs, two different cost schemes are explored: one linear and one nonlinear. Computational experiments using real data from a national LTL carrier compare the total system costs obtained with four different strategies and show that extra repositioning may indeed enable fleet size reductions and concomitant cost savings.     

Designing robust liner shipping schedules: Optimizing recovery actions and buffer times

It is important for liner shipping companies to maintain cost efficient and robust liner shipping networks. Regularly, they set up pro-forma schedules, yet it is difficult to stay on time. We consider the problem of managing the delays. Therefore, we need to determine an optimal recovery policy and buffer time allocation to the ship route in order to minimize the total costs associated with delays and recovery actions, such as increasing sailing speed. We introduce a general framework consisting of a mixed integer programming formulation to solve discrete stochastic decision problems with short and long term decisions and apply this framework to the above described problem. Furthermore, we propose and test four heuristics for this problem. We compared the results of our method with an existing liner shipping route schedule and found a cost decrease of 28.9% after optimizing the buffer time distribution compared to the cost of sailing the current route schedule at constant speed.     

Scheduling policies for a repair shop problem

In this paper, we analyze a repair shop serving several fleets of machines that fail from time to time. To reduce downtime costs, a continuous-review spare machine inventory is kept for each fleet. A spare machine, if available on stock, is installed instantaneously in place of a broken machine. When a repaired machine is returned from the repair shop, it is placed in inventory for future use if the fleet has the required number of machines operating. Since the repair shop is shared by different fleets, choosing which type of broken machine to repair is crucial to minimize downtime and holding costs. The optimal policy of this problem is difficult to characterize, and, therefore, is only formulated as a Markov Decision Process to numerically compute the optimal cost and base-stock level for each spare machine inventory. As an alternative, we propose the dynamic Myopic(R) policy, which is easy to implement, yielding costs very close to the optimal. Most of the time it outperforms the static first-come-first-served, and preemptive-resume priority policies. Additionally, via our numerical study, we demonstrate that repair shop pooling is better than reserving a repair shop for each fleet.     

Approximative solutions to the bicriterion Vehicle Routing Problem with Time Windows

The Vehicle Routing Problem with Time Windows (VRPTW) is a combinatorial optimization problem. It deals with route planning and the distribution of goods from a depot to geographically dispersed customers by a fleet of vehicles with constrained capacities. The customers’ demands are known and each customer has a time window in which it has to be supplied. The time windows are assumed to be soft, that means, violations of the time windows are allowed, but associated with penalties. The problem is to organize the vehicle routes optimally, i.e. to minimize the total costs, consisting of the number of used vehicles and the total distance, and the penalties simultaneously. Thus, the problem is formulated as a bicriterion minimization problem and heuristic methods are used to calculate approximations of the Pareto optimal solutions. Experimental results show that in certain cases the allowance of penalties leads to significant savings of the total costs.     

A perturbation metaheuristic for the vehicle routing problem with private fleet and common carriers

The purpose of this article is to propose a perturbation metaheuristic for the vehicle routing problem with private fleet and common carrier (VRPPC). This problem consists of serving all customers in such a way that (1) each customer is served exactly once either by a private fleet vehicle or by a common carrier vehicle, (2) all routes associated with the private fleet start and end at the depot, (3) each private fleet vehicle performs only one route, (4) the total demand of any route does not exceed the capacity of the vehicle assigned to it, and (5) the total cost is minimized. This article describes a new metaheuristic for the VRPPC, which uses a perturbation procedure in the construction and improvement phases and also performs exchanges between the sets of customers served by the private fleet and the common carrier. Extensive computational results show the superiority of the proposed metaheuristic over previous methods.     

Optimal empty vehicle repositioning and fleet-sizing for two-depot service systems

This paper considers the problem of determining optimal control policies for empty vehicle repositioning and fleet-sizing in a two-depot service system with uncertainties in loaded vehicle arrival at depots and repositioning times for empty vehicles in the fleet. The objective is to minimise the sum of the costs incurred by vehicle maintenance, empty vehicle repositioning and vehicle leasing. A novel integrated model is presented. The optimal empty repositioning policy for a particular fleet size is shown to be of the threshold control type. The explicit form of the cost function under such threshold controls is obtained. The optimal threshold values and fleet-size are then derived. Numerical examples are given to demonstrate the results.     

Implicit depot assignments and rotations in vehicle routing heuristics

Vehicle routing variants with multiple depots and mixed fleet present intricate combinatorial aspects related to sequencing choices, vehicle type choices, depot choices, and depots positioning. This paper introduces a dynamic programming methodology for efficiently evaluating compound neighborhoods combining sequence-based moves with an optimal choice of vehicle and depot, and an optimal determination of the first customer to be visited in the route, called rotation. The assignment choices, making the richness of the problem, are thus no more addressed in the solution structure, but implicitly determined during each move evaluation. Two meta-heuristics relying on these concepts, an iterated local search and a hybrid genetic algorithm, are presented. Extensive computational experiments demonstrate the remarkable performance of these methods on classic benchmark instances for multi-depot vehicle routing problems with and without fleet mix, as well as the notable contribution of the implicit depot choice and positioning methods to the search performance. New state-of-the-art results are obtained for multi-depot vehicle routing problems (MDVRP), and multi-depot vehicle fleet mix problems (MDVFMP) with unconstrained fleet size. The proposed concepts are fairly general, and widely applicable to many other vehicle routing variants.     

Equipment Replacement in an Unsteady Economy

The decision problem concerning the replacement of members of a fleet of fork lift trucks during a period of inflation and economic uncertainty is considered. Based upon the analysis of data collected over a 2 year period of considerable inflation, a model of the expected operating costs for a truck is developed. The usual replacement criteria are not applicable here and an alternative criterion function based upon relatively short term estimates of costs and discount rate is presented. Using this function, the replacement decision is determined for both constant and variable discount rate situations.     

A survey of recent research on location-routing problems

The design of distribution systems raises hard combinatorial optimization problems. For instance, facility location problems must be solved at the strategic decision level to place factories and warehouses, while vehicle routes must be built at the tactical or operational levels to supply customers. In fact, location and routing decisions are interdependent and studies have shown that the overall system cost may be excessive if they are tackled separately. The location-routing problem (LRP) integrates the two kinds of decisions. Given a set of potential depots with opening costs, a fleet of identical vehicles and a set of customers with known demands, the classical LRP consists in opening a subset of depots, assigning customers to them and determining vehicle routes, to minimize a total cost including the cost of open depots, the fixed costs of vehicles used, and the total cost of the routes. Since the last comprehensive survey on the LRP, published by Nagy and Salhi (2007), the number of articles devoted to this problem has grown quickly, calling a review of new research works. This paper analyzes the recent literature (72 articles) on the standard LRP and new extensions such as several distribution echelons, multiple objectives or uncertain data. Results of state-of-the-art metaheuristics are also compared on standard sets of instances for the classical LRP, the two-echelon LRP and the truck and trailer problem.     

Optimal control of road freight flows by route choice inducement: A case from Mexico

Contrasting with much of the research in freight transportation around the impacts to transport operators, this work focuses on the Road Planner providing the infrastructure. This viewpoint, seeking minimal repair costs and other payments generally conflicts with the carriers’ view, looking for the best hauling route.On a random utility frame, the user-planner interaction is modelled on a partially tolled road network, considering two types of costs: (a) lorries’ trip cost guiding the route choice, and affected by planners’ actions, and (b) planners’ road repair costs, depending on the traffic, the vehicles’ type and the control implementation. A Monte Carlo simulation bases the stochastic assignment on the network, determining optimal subsidies that divert traffic to tolled roads. On a portion of the Mexican Paved network optimal subsidies are found, increasing the toll roads’ use and reducing traffic on the non-charged roads, generally having weaker pavements and higher maintenance costs.     

Minimizing fleet operating costs for a container transportation company

This paper focuses on a fleet management problem that arises in container trucking industry. From the container transportation company perspective, the present and future operating costs to minimize can be divided in three components: the routing costs, the resource (i.e., driver and truck) assignment costs and the container repositioning costs (i.e., the costs of restoring a given container fleet distribution over the serviced territory, as requested by the shippers that own the containers).This real-world problem has been modeled as an integer programming problem. The proposed solution approach is based on the decomposition of this problem in three simpler sub-problems associated to each of the costs considered above.Numerical experiments on randomly generated instances, as well as on a real-world data set of an Italian container trucking company, are presented.     

A Method for Finding the Shortest Route Through a Road Network

When a new road is being planned it is necessary to assess how much traffic will be diverted to it from various parts of the existing road network. This allocation of traffic has usually been based on a comparison of journey times or journey costs on alternative routes, and has depended on the selection, by trial and error, of the cheapest route through the network.A method is described which determines the shortest or cheapest routes between points on the network and which can readily be extended to show how traffic between the points is distributed and to assess the total cost of vehicle operation on the network.The procedure is quite systematic and independent of the manner in which journey costs are derived, and it could be carried out on an electronic computer with considerable saving in time. It can be applied to any transportation or communication problem that involves finding the most economical routes through a network.     

An integral LP relaxation for a drayage problem

This paper investigates a drayage problem, where a fleet of trucks must ship container loads from a port to importers and from exporters to the same port, without separating trucks and containers during customer service. We present three formulations for this problem that are valid when each truck carries one container. For the third formulation, we also assume that the arc costs are equal for all trucks, and then we prove that its continuous relaxation admits integer optimal solutions by checking that its constraint matrix is totally unimodular. Under the same hypothesis on costs, even the continuous relaxations of the first two models are proved to admit an integer optimal solution. Finally, the third model is transformed into a circulation problem, that can be solved by efficient network algorithms.     

Dynamic navigation field in the social force model for pedestrian evacuation

This paper presents a generalized walking cost distribution to determine a dynamic navigation field in the social force model for pedestrian evacuation. The local walking cost per unit distance of movement includes the cost associated with travel time and other additional costs incurred by pedestrians to avoid colliding with obstacles in a dynamic environment. In the dynamic navigation field, pedestrians expect to choose an optimal path with the lowest walking cost to reach their target destination reactively based on available instantaneous information. The social force model with the dynamic navigation field is validated by comparing the simulation results with empirical observations. The fundamental diagrams for observations and simulation data agree well, which indicates the effectiveness of the model. Numerical results show that the model with the dynamic navigation field can reproduce typical stages of the dynamics of pedestrian evacuation, such as self-organized arching and queuing phenomena, and can capture the route choice and exit choice behaviors of pedestrians during the evacuation process. Compared to the model with the static navigation field, the model with the dynamic navigation field can reduce the total evacuation time of the room and save the required CPU time for a large group of pedestrians. Furthermore, the strong tendency to avoid local high-density regions (i.e., minimizing collisions) can also reduce the total evacuation time under the same conditions.     

An Equipment Replacement Problem

This paper describes a study undertaken to develop a model for the replacement of a particular type of machine. The dominant operating costs are identified, and existing replacement models reviewed. One of the most important factors is the cost of production stoppages which can sometimes result from the breakdown of these machines. In order to predict the effects of this in terms of the machines' age, a simulation model is developed.The results from the replacement model are investigated in terms of their sensitivity to the variability in the estimates of the parameters required by the model. In particular some interesting results relating the method used for calculating the resale values and the optimal replacement interval are presented.     

Integer programming by long division

We present a formal long-division algorithm for solving the well-known group minimisation problem. In fact, given some group elements with associated positive costs, the algorithm produces a listing of all products of these elements, in ascending order of total cost. It may thus be applied to the solution of all-integer linear programs, by finding the cheapest solution to the group minimisation problem consistent with feasibility.     

Planung der geringsten Kosten täglicher lokaler Lieferungen. Ein Beispiel für die Anwendung der Dynamischen Planung

Zusammenfassung Die Planung der täglichen Lieferung von Waren vom Erzeuger zum Verbraucher unter Benützung von Transportunternehmen und des firmeneigenen Lastwagenparkes stellt ein ziemlich schwieriges alltägliches Entscheidungsproblem dar, da die Variablen der Zuweisung diskret und normalerweise zahlreich sind. Bei verschieden großen Lastwagenparks ist im Hinblick auf die geringsten Gesamt-Lieferkosten nicht unbedingt jene Zuteilung von Lieferaufträgen die günstigste, bei welcher die eigenen Lastwagen täglich voll ausgelastet werden, und die von Tag zu Tag anzusetzenden Lieferungen können hinsichtlich ihrer Art und Anzahl stark variieren.Ein solches Planungsproblem wurde im Detail studiert. Die vorliegende Unterlage enthält die Ergebnisse dieser Untersuchung.Mit Hilfe von Rekursionsmethoden (Dynamische Planung) und unter genauer Berücksichtigung der speziellen Eigenschaften der betreffenden Kostenfunktion kann man eine einfache Regel für die Wahl jener Lieferpläne, die ein ungefähres Optimum darstellen, finden, sowie einen Ausdruck für die Grenze der Abweichung von den genauen sich ergebenden Mindestkosten festlegen. Klarerweise ist diese Grenze sehr eng gesteckt, und es ist weder wünschenswert noch notwendig, die Planung auf die genauen Mindestkosten abzustellen, vor allem im Hinblick auf die Tatsache, daß der Möglichkeit, präzise Kosteninformationen zu erhalten, praktische Grenzen gesetzt sind und es sehr schwer ist, täglich eine genaue Berechnung des Optimalplanes durchzuführen.Sobald eine Entscheidungsregel für einen annähernd optimalen Tages-Lieferplan aufgestellt ist, ergibt sich natürlich die Frage der Optimalgröße des eigenen Lastwagenparks. Man kann für verschiedene hypothetische Größen des Wagenparks Kostenvergleichsberechnungen in bezug auf die im unmittelbar vergangenen Jahr vorhandene Liefersituation anstellen, wobei man die Entscheidungsregel für den annähernd optimalen Lieferplan als Grundlage für die Bestimmung der Mindest-Betriebskosten für jeden einzelnen Wagenpark nimmt und Lastwagen von Jahr zu Jahr aus dem Dienst zieht oder neu ankauft, um den Wagenpark in der Nähe der Optimalgröße zu halten. Der hier vorgeschlagene Planungsabschnitt, nämlich ein Jahr, kann länger oder kürzer gewählt werden, je nach den näheren Umständen des Marktes und den Usancen bei Kapitalinvestitionen und deren Versicherung. Auf diese Weise kann man erreichen, daß die Leiferkosten ziemlich in der Nähe des Minimums gehalten werden, vorausgesetzt daß die saisonbedingten Schwankungen in der durchschnittlichen Anzahl und der Art der täglichen Lieferungen nicht von Planungsperiode (d. h. Jahr) zu Planungsperiode allzu sehr verschieden sind. Wenn die Unterschiede von Jahr zu Jahr groß sind, kann die Aufgabe, einen optimalen Wagenpark zu finden, tatsächlich sehr kompliziert werden, da die Vorhersage der saisonbedingten Schwankungen im durchschnittlichen Tagesvolumen allein nicht genügt, sondern evtl. auch Änderungen in der Art (d. h. Lieferzeit und Lieferumfang) der Lieferungen ebenfalls vorhergesagt werden müssen.Gleichgültig, wie genau die Optimalgröße des Lastwagenparks bestimmt werden kann, bleibt es doch wichtig, eine annähernd optimale Entscheidungsregel für die Verteilung der täglichen Lieferungen auf eigene Lastwagen und Transportunternehmen zu finden. Die Einsatzentscheidung muß Tag für Tag getroffen werden, gleichgültig, wie zutreffend die Entscheidung über die Investition in firmeneigenen Lastwagen war; dabei kann es um beträchtliche Geldsummen gehen, vor allem in unserem Beispiel, wo die Lieferkosten einen wesentlichen Teil der Gesamtkosten ausmachten. In manchen Fällen lassen sich die größten Einsparungen durch eine richtige Einschätzung der Optimalgröße des firmeneigenen Lastwagenparks erzielen.

---

Summary The scheduling, between common carrier and private fleet truck, of local delivery of product from manufacturer to customer is a daily decision problem of some complexity, because the assignment variables are discreet and ordinarily many in number. For any given size of private truck fleet, the most efficient assignment of deliveries (in the sense of least total delivery costs) is not necessarily one in which a private fleet is used to capacity each day, and the deliveries to be scheduled each day may be highly variable in number and kind.This scheduling problem has been studied in detail for a manufacturer of glass containers. The results of this study are reported herein.By use of recursion methods (Dynamic programming) and explicit consideration of the special properties of the cost function involved, a simple decision rule is found for scheduling deliveries which is approximately optimum, and an expression is given for a bound upon the deviation from exact minimum cost thereby entailed. The bound is evidently small and an exact minimum cost scheduling is neither desirable nor required, particularly in view of the practical limitations of getting precise cost data and the difficulties of making daily an exact calculation of optimum scheduling.Having determined an approximately optimum daily scheduling decision rule, the question of optimum private, truck fleet size naturally arises. Comparative cost calculations may be made for various hypothetical private fleet sizes related to the deliveries encountered during an immediately previous year, using the near optimum daily scheduling rule as a basis for determining minimum operating costs connected with each fleet size, and private trucks may be retired or purchased annually to control the private fleet at near optimum size. The planning period suggested, i. e. one year, may be increased or decreased, depending upon the market circumstances and practices used for making and underwriting capital investments. The control thus obtained will be comparatively close to a minimum for delivery costs, provided the seasonal variation of average daily number and character of deliveries do not fluctuate violently from one planning period (e. g. year) to the next. If the annual variation is great, the problem of optimizing fleet size may be complex indeed, because forecasts of the seasonal variation of average daily volume alone are not sufficient. Changes in the character (i. e. destination and related volume of goods) of deliveries may have to be forecasted.Regardless of how well an optimum fleet size can be determined, it is important to have an approximately optimum daily decision rule for assignment of deliveries between private truck and common carrier. The operating decision to be made arises day by day, no matter how well the decision for investment in company trucks has been made, and considerable funds may be at stake, particularly in the case study presented here where delivery costs are a substantial part of total costs. The largest savings may be derived, in some instances, from correctly assessing the optimum size of private truck fleet.