基于双层规划的高速公路收费费率优化模型

在全国联网收费的背景下,从动态收费的角度考虑,建立了双层规划模型,上层规划中将路网管理者作为领导者,以高速公路收费效益最大化为目标函数,同时考虑道路运营管理方的合理收益和养护成本支出情况,下层规划则以用户出行效用最大化为目标,充分考虑了道路使用者的道路选择差异性及道路拥堵对交通分布的影响,建立随机用户均衡模型.最后结合某地区AB地高速公路实际情况进行分析,采用了遗传模拟退火算法验证了模型的实用性,并与其他的算法对比,验证了算法的有效性。研究表明:优化模型可以有效提高高速公路的收费效益和用户的出行效用,可以分散高峰时的交通压力,提升高速公路的通行效率.     

District design for arc-routing applications

In this paper we address the problem of district design for the organisation of arc-routing activities. In particular, the focus is on operations like winter gritting and road maintenance. The problem involves how to allocate the road network edges to a set of depots with given locations. The collection of edges assigned to a facility forms a district in which routes have to be designed that start and end at the facility. Apart from the ability to support good arc routing, well-designed districts for road-maintenance operations should have the road network to be serviced connected and should define clear geographical boundaries. We present three districting heuristics and evaluate the quality of the partitions by solving capacitated arc routing problems in the districts, and by comparing the solution values with a multi-depot CARP cutting plane lower bound. Our experiments reveal that based on global information about the distribution system (ie the number of facilities or districts, the average edge demand and the vehicle capacity) and by using simple guidelines, an adequate districting policy may be selected.     

Measuring the efficiency of highway maintenance contracting strategies: A bootstrapped non-parametric meta-frontier approach

Highly deteriorated US road infrastructure, major budgetary restrictions and the significant growth in traffic have led to an emerging need for improving performance of highway maintenance practices. Privatizing some portions of road maintenance operations by state Departments of Transportation (DOTs) under the auspices of performance-based contracts has been one of the innovative initiatives in response to such a need. This paper adapts the non-parametric meta-frontier framework to the two-stage bootstrapping technique to develop an analytical approach for evaluating the relative efficiency of two highway maintenance contracting strategies. The first strategy pertains to the 180 miles of Virginia’s Interstate highways maintained by Virginia DOT using traditional maintenance practices. The second strategy pertains to the 250 miles of Virginia’s Interstate highways maintained via a Public Private Partnership using a performance-based maintenance approach. The meta-frontier approach accounts for the heterogeneity that exists among different types of highway maintenance contracts due to different limitations and regulations. The two-stage bootstrapping technique accounts for the large set of uncontrollable factors that affect the highway deterioration processes. The preliminary findings, based on the historical data for the state of Virginia, suggest that road authorities (counties) that have used traditional contracting for transforming the maintenance expenditures into the improvement of the road conditions seem to be more efficient than road authorities that have used the performance-based contracting. This paper recommends that road authorities use hybrid contracting approaches that include best practices of both traditional and performance-based highway maintenance contracting.     

The periodic capacitated arc routing problem with irregular services

The aim of this paper is to introduce the periodic capacitated arc routing problem with irregular services. Some applications can be found in road maintenance operations and road network surveillance. The problem consists of determining a set of routes to cover a given network over a time horizon. The roads must be serviced a number of times in sub-periods over the time horizon, according to a hierarchy of arc classes. We present a mathematical model and a heuristic solution approach.     

A branch-and-price approach for operational aircraft maintenance routing

In recent years, considerable effort in the field of operations research has been paid to optimizing airline operations, including the logistics of an airline’s fleet of aircraft. We focus on the problem of aircraft routing, which involves generating and selecting a particular route for each aircraft of a sub-fleet that is already assigned to a set of feasible sequences of flight legs. Similar studies typically focus on long-term route planning. However, stochastic events such as severe weather changes, equipment failures, variable maintenance times, or even new regulations mandated by the Federal Aviation Administration (FAA) play havoc on these long-term plans. In addition, these long-term plans ignore detailed maintenance requirements by considering only one or two of the primary maintenance checks that must be performed on a regular, long-term basis. As a result, these plans are often ignored by personnel in airline operations who are forced on a daily basis to develop quick, ad hoc methods to address these maintenance requirements and other irregular events. To address this problem, we develop an operational aircraft maintenance routing problem formulation that includes maintenance resource availability constraints. We propose a branch-and-price algorithm for solving this problem, which, due to the resource constraints, entails a modification of the branch-on, follow-on branching rule typically used for solving similar problems. Through computational testing, we explore the efficiency of this solution approach under a combination of heuristic choices for column (route) generation and selection.     

Scheduling farm operations

Scheduling operations on a farm is considered depending on the available men and machinery and on the influence of the weather on materials (moisture content). A simulation model with a heuristic strategy for selecting operations at each moment of decision based on the state of the system and a linear programming model are used in the grain harvest to demonstrate the influence of the models on the resulting variable costs (overtime, drying of wet grain and timeliness losses of wheat and straw) and the influence of input data (weather, attributes of material and number of workable hours) on those costs. The lower costs found with simplified input (hourly, daily, weekly data) in simulation is continued with the linear programming model due to its deviation from the real workable time constraints and decision variables. Such a tendency suggests that LP-models usual in agricultural planning are too simple.     

The sector design and assignment problem for snow disposal operations

Winter road maintenance operations involve a host of decision-making problems at the strategic, tactical, operational, and real-time levels. Those operations include spreading of chemicals and abrasives, snow plowing, loading snow into trucks, and hauling snow to disposal sites. In this paper, we present a model and two heuristic solution approaches based on mathematical optimization for the problem of partitioning a road network into sectors and allocating sectors to snow disposal sites for snow disposal operations. Given a road network and a set of planned disposal sites, the problem is to determine a set of non-overlapping subnetworks, called sectors, according to several criteria related to the operational effectiveness and the geographical layout, and to assign each sector to a single snow disposal site so as to respect the capacities of the disposal sites, while minimizing relevant variable and fixed costs. Our approach uses single street segments as the units of analysis and we consider sector contiguity, sector balance and sector shape constraints, hourly and annual disposal site capacities, as well as single assignment requirements. The resulting model is based on a multi-commodity network flow structure to impose the contiguity constraints in a linear form. The two solution approaches were tested on data from the city of Montreal in Canada.     

Managing a portfolio of long term service agreements

Long-term service agreements (LTSAs) for the maintenance of capital-intensive equipments such as gas turbines and aircraft engines are gaining wide acceptance. A typical LTSA contract spans over a period of around 10 years making a manufacturer fully responsible for maintaining the customer equipment. In this paper, we address the management of a portfolio of such contracts from the manufacturer’s perspective. The goal is to meet all the service requirements imposed by the contracts while minimizing total cost incurred. We develop a deterministic integer programming model to generate the optimal maintenance schedules that minimize the total portfolio cost. We then propose two heuristic algorithms for the problem.     

Modelling and Optimal Receding-horizon Control of Maritime Container Terminals

The main objective of this paper consists in modelling, optimizing, and controlling container transfer operations inside intermodal terminals. More specifically, maritime container terminals are here considered, involving three kinds of transportation modes, i.e., maritime, rail, and road transport. Generally speaking, an intermodal port terminal can be seen as a system of container flows with two interfaces, towards the hinterland and towards the sea, respectively. Moreover, inside a terminal, unloading operations of inbound containers, container storage, and loading operations of outbound containers are carried out. A simple model for maritime container terminals is proposed in this paper. In the model, a system of queues represents the standing of containers and their movements inside the terminal. The dynamic evolutions of these queues are described by discrete-time equations, where the state variables represent the queue lengths and the control variables take into account the utilization of terminal resources such as load/unload handling rates. On the basis of the proposed model, an optimization problem is defined that consists in minimizing the transfer delays of containers in the terminal. The problem is stated as an optimal control problem whose solution is sought by adopting a receding-horizon strategy.      

Multiple feedback at a single-server station

A single server facility is equipped to perform a collection of operations. The service rendered to a customer is a branching process of operations. While the performance of an operation may not be interrupted before its completion, once completed, the required follow-up work may be delayed, at a cost per unit time of waiting that depends on the type and load of work being delayed. Under some probabilistic assumptions on the nature of the required service and on the stream of customers, the problem is to find service schedules that minimize expected costs. The authors generalize results of Bruno [2], Chazan, Konheim and B. Weiss [4], Harrison [8], Klimov [10], Konheim [11], and Meilijson and G. Weiss [13], using a dynamic programming approach.     

Scheduling of road vehicles in sugarcane transport: A case study at an Australian sugar mill

Pressure to remain internationally competitive has forced Australian sugar mills to reduce capital and operational costs. Improved scheduling of road transport vehicles provides one such opportunity, as it would reduce vehicle queue and mill idle times and hence the number of vehicles needed. It is difficult for mill traffic officers to produce good transport schedules manually due to the need to service a large number of harvesters in different locations. To address this issue, research was undertaken participatively with a sugar milling company in Australia to produce and implement a mixed integer programming model that represents the road transport operations. Two meta-heuristics were applied to find a solution to the model, leading to potential cost savings of AU$240,000 per year versus schedules produced manually by the mill traffic officer. The model was also applied to explore regional planning options for a more integrated harvesting and transport system.     

OD估计双层规划扩展模型

利用双层规划模型进行OD估计,建立双层规划扩展模型.考虑OD估计问题中的随机误差,基于Bayes估计和多元正态分布建立上层目标函数;考虑用户路径选择行为的随机性,基于随机用户均衡建立需求可变动的下层目标函数,同时该扩展模型能适应我国混合交通的实际,既能适用于拥挤网络、也能适用于非拥挤网络,最后通过算例证明此模型的有效性.     

An airline scheduling model and solution algorithms under stochastic demands

When setting a good flight schedule airlines not only have to consider their fleet supply and related operations, as well as market share, but also stochastic variations caused by daily passenger demands in actual operations. Most of the past research on short-term flight scheduling has used the average passenger demand as input to produce the final timetable and schedule, which means that daily passenger variations that occur in actual operations are neglected. To consider such stochastic disturbances we developed a stochastic-demand scheduling model. We employed arc-based and route-based strategies to develop two heuristic algorithms that can be used to solve the model. The test results, based on a major Taiwan airline’s operation, show the good performance of the model and the solution algorithms.     

A mathematical model and algorithms for the aircraft hangar maintenance scheduling problem

An aircraft hangar maintenance scheduling problem is studied, motivated by the aircraft heavy maintenance conducted in a hangar operated by an independent maintenance service company. The aircraft hangar maintenance scheduling problem in such context consists of determining a maintenance schedule with minimum penalty costs in fulfilling maintenance requests, and a series of hangar parking plans aligned with the maintenance schedule through the planning period. A mixed-integer linear programming (MILP) mathematical model, integrating the interrelations between the maintenance schedule and aircraft parking layout plans, is presented at first. In the model, the variation of parking capacity of the maintenance hangar and the blocking of the aircraft rolling in and out path are considered. Secondly, the model is enhanced by narrowing down the domain of the time-related decision variables to the possible rolling in and out operations time of each maintenance request. Thirdly, to obtain good quality feasible solutions for large scale instances, a rolling horizon approach incorporating the enhanced mathematical model is presented. The results of computational experiments are reported, showing: (i) the effectiveness of the event-based discrete time MILP model and (ii) the scalability of the rolling horizon approach that is able to provide good feasible solutions for large size instances covering a long planning period.     

Consolidating Maintenance Spares

The inventory of spare parts that a firm holds depends on the number of working parts and age of the equipment to be serviced, the expected failure rate associated with each working part, and the acceptable level of service. We model the problem of consolidation of spare parts to reduce overall inventory as an integer program with a nonlinear objective function. A linear reformulation of this model is obtained that helps solve some practical instances. A more compact implicit formulation is developed and solved using a specialized branch-and-price technique. We also demonstrate how this specialized branch-and-price technique is modified to devise a very effective heuristic procedure with a prespecifiable guarantee of quality of solution produced. This provides a practical and efficient methodology for maintenance spare consolidation.     

A fuzzy system for municipalities classification

A knowledge-based fuzzy system for the purpose of municipalities classification is presented in this paper. It illustrates how fuzzy systems can be used for municipalities classification and ranking tasks. The application of the system is explained by the example of classification in one region in the Slovak Republic. The original problem of estimating and rough planning of road maintenance requirements in winter was examined. The suggested methodology is supported by GIS technology for visualization of the ranked municipalities to offer a better view on the territorial distribution of the obtained solution. A disadvantage of fuzzy systems for the end user is in their complexity. This disadvantage has been analysed and a solution is suggested to overcome it. The proposal deals with the integration of information system and self developed fuzzy system. This integration enables creating the model, importing input data, processing rules and presenting results in tables and maps in one integrated tool.     

Optimal control of a facility with periodic interrupted demand

The system investigated consists of a stochastic periodic stream of raw material, a continuous processing operation with controllable deterministic service rates, and a storage facility. The arrival stream is periodically interrupted and divided into alternating on-off intervals of fixed length. The processing facility is allowed to operate during the off-interval. Superimposed on this system is a cost structure composed of processing and holding costs. Such operations may be found in manufacturing as well as service systems (for example, dry cleaners, machine shops, repair and maintenance shops, printers, information processing centers, etc). A service rate control rule that minimizes the infinite-horizon discounted expected total cost is found. Existence and uniqueness of long-term optimal cost and policy functions is shown. Since the optimal policy cannot be expressed explicitly, an approximate solution was obtained. An error bound on the optimal cost associated with this solution is exhibited. The approximate solution is characterized by a service rate control rule that is a linear function of the level of inventory at the start of each on-interval and a piecewise linear function of inventory at the start of each off-interval. The optimal discounted expected total cost is quadratic in the inventory level at the start of each interval. Computational results indicate relative cost errors in the order of 2–3 percent.This research was performed at the Sanitary Engineering Research Laboratory and Operations Research Center of the University of California, Berkeley. It was made possible by US Public Health Research Grant UI-00547 from the Environmental Control Administration-Bureau of Solid Waste Management and by National Science Foundation Grant GK-1684.The author thanks Professor C. R. Glassey for not only suggesting this research, but for his constant encouragement and suggestions throughout its duration. He also thanks Professors W. S. Jewell and P. H. McGauhey whose comments on the draft were very helpful.     

A fuzzy programming approach for dynamic virtual hub location problem

Hub location problem has been used in transportation network to exploit economies of scale. For example, a controversial issue in the planning of air transportation networks is inclement weather or emergency conditions. In this situation, hub facilities would not be able to provide a good service to their spoke nodes temporarily. Thus, some other kinds of predetermined underutilized facilities in the network are used as virtual hubs to host some or all connections of original hubs to recover the incurred incapacitation and increase network flexibility and demand flow. In such an unexpected situation, it is not unreasonable to expect that some information be imprecise or vague. To deal with this issue, fuzzy concept is used to pose a more realistic problem. Here, we present a fuzzy integer liner programming approach to propose a dynamic virtual hub location problem with the aim of minimizing transportation cost in the network. We examine the effectiveness of our model using the well-known CAB data set.     

A cost effectiveness approach for determining the purchasing and operating policies of a combined meteorological data gathering system

The model we present in this paper was developed to solve a meteorological equipment operations problem involving the purchase and operation of specialized aircraft for the gathering of meteorological data. This aircraft system (termed ‘System B’) will be used to supplement an existing system using weather balloons (termed ‘System A’). The problem involves decision making based upon bi-criterion objectives. These objectives usually occur in the presence of one or both of the following factors: (a) The outputs of the systems have more than one attribute and (b) the outputs may be measured under varying environmental situations. The specific type of problem treated here involves a two objective situation arising from the latter factor. It was found out that due to the nature of this problem it was difficult to implement a utility approach to generate a solution. Therefore, a cost-effectiveness approach is presented to demonstrate a technique for finding the trade-off function between objectives for varying levels of systems and operating characteristics. This approach is similar to that of Subramanian and Ravichandran [8] where a complex two-unit electronic system was studied.     

Optimal maintenance service contract negotiation with aging equipment

In recent years, there has been a growing trend to out-source service operations in which the equipment maintenance is carried out by an external agent rather than in-house. Often, the agent (service provider) offers more than one option and the owners of equipment (customers) are faced to the problem of selecting the optimal option, under the terms of a contract. In the current work, we develop a model and report results to determine the agent’s optimal strategy for a given type of contract. The model derives in a non-cooperative game formulation in which the decisions are taken by maximizing expected profits. This work extends previous models by considering the realistic case of equipments having an increasing failure intensity due to imperfect maintenance, instead of the standard assumption that considers failure times are exponentially distributed (constant failure intensity). We develop a model using a linear function of time to characterize the failure intensity. The main goal, for the agent, is to determine the pricing structure in the contract and the number of customers to service. On the other hand, for the clients, the main goal is to define the period between planned actions for preventive maintenance and the time to replace equipments. In order to give a complete characterization of the results, we also carry out a sensitivity analysis over some of the factors that would influence over the failure intensity.