Flexible-term contracts for road franchising

Private participation in road projects is increasing around the world. The most popular form of franchising is a concession contract, which allows a private firm to charge tolls to road users during a pre-determined period in order to recover investments. Concessionaires are usually selected through auctions at which candidates submit bids for tolls or payments to the government. This paper discusses how this mechanism does not generally yield optimal outcomes and it induces the frequent contract renegotiations observed in practice. A new franchising mechanism is proposed, based on a flexible-term contract and bi-dimensional bids for total net revenue and maintenance costs. This new mechanism improves outcomes compared to fixed-term concessions, by eliminating traffic risk and promoting the selection of efficient concessionaires.     

Sealed v/s open bids for certificates of entitlement under the vehicle quota system in Singapore

The Vehicle Quota System manages vehicle ownership in Singapore by making the procurement of a Certificate of Entitlement (COE) a prerequisite for the registration of a new vehicle. The procurement is done during uniform price auctions of quotas of COEs currently held on a twice-a-month schedule. The auction format which started out as sealed bids in May 1990 changed to open bids in July 2001. This paper uses a regression model framework to investigate if this shift in auction format has resulted in lower COE premium volatility and a better reflection of demand and supply forces. The empirical results are pertinent to transport policy analysis. A suggestion in the form of incentives for early bids is also made to improve the efficiency of the open bids auction.     

Optimising the control performance of traffic signals at a single junction

The optimal control performance of a single signal-controlled junction is investigated. Two existing methods for analysing this control problem are discussed. One of these, a combinatorial method, generates all possible control structures in terms of groupings of streams of traffic to have green together and the order in which right of way is granted. The other method allows an existing control structure to be optimised by convex programming techniques. Incompatibilities between these two approaches are illustrated and it is shown that they cannot be combined in a satisfactory manner. A new procedure is framed that allows a control structure generated by the combinatorial method to be optimised directly. This procedure is applied to an example junction to illustrate its use.     

A reinforcement learning framework for the adaptive routing problem in stochastic time-dependent network

Most previous work in addressing the adaptive routing problem in stochastic and time-dependent (STD) network has been focusing on developing parametric models to reflect the network dynamics and designing efficient algorithms to solve these models. However, strong assumptions need to be made in the models and some algorithms also suffer from the curse of dimensionality. In this paper, we examine the application of Reinforcement Learning as a non-parametric model-free method to solve the problem. Both the online Q learning method for discrete state space and the offline fitted Q iteration algorithm for continuous state space are discussed. With a small case study on a mid-sized network, we demonstrate the significant advantages of using Reinforcement Learning to solve for the optimal routing policy over traditional stochastic dynamic programming method. And the fitted Q iteration algorithm combined with tree-based function approximation is shown to outperform other methods especially during peak demand periods.     

Use of combinatorial auctions in the railway industry: Can the “invisible hand” draw the railway timetable?

Rail capacity is currently administratively allocated in Europe, whereas the economic literature has often contemplated the opportunity of introducing market mechanisms, auctions in particular, into this industry. This article tries to fill the gap between practice and theory. It first describes the properties of rail capacity (rigidity and non-homogeneity) and shows that because of its very nature, this capacity must be allocated through combinatorial auctions. As identified by the economic literature, using combinatorial auctions introduces a lot of complexity (winner determination and information burden) into the allocation process. To deal with this complexity, some form of centralized planning is necessary to design the right market mechanisms and to allocate capacity. This could have strong consequences on the current deregulation process.     

Dynamic threshold policy for delaying and breaking commitments in transportation auctions

In this paper we consider a transportation procurement auction consisting of shippers and carriers. Shippers offer time sensitive pickup and delivery jobs and carriers bid on these jobs. We focus on revenue maximizing strategies for the shippers in sequential auctions. For this purpose we propose two strategies, namely delaying and breaking commitments. The idea of delaying commitments is that a shipper will not agree with the best bid whenever it is above a certain reserve price. The idea of breaking commitments is that the shipper allows the carriers to break commitments against certain penalties. We evaluate the benefits of both strategies with simulation. In addition, we provide insight into the distribution of the lowest bid which is estimated by the shippers.     

Cargo Container Loading Plan Model and Solution Method for International Air Express Carriers

Abstract

In this article, a cargo container loading plan model is developed based on the operations of FedEx, the international air express carrier. The objective is to minimize total container handling cost, subject to related operating constraints. The model is expected to be a useful planning tool whereby international air express carriers such as FedEx can decide on container loading plans that will lead to lower operating costs, thus enhancing profits and market competitiveness. The model is formulated as a non-linear mixed integer program that is characterized as NP-hard. A solution method is then developed, with the use of the mathematical programming solver, CPLEX, to solve the problem efficiently. To evaluate the model and the solution method, we perform a case study using data from FedEx. The preliminary results indicate that the model and the solution method are both efficient and effective.     

Solving the gate assignment problem through the Fuzzy Bee Colony Optimization

In the field of Swarm Intelligence, the Bee Colony Optimization (BCO) has proven to be capable of solving high-level combinatorial problems, like the Flight-Gate Assignment Problem (FGAP), with fast convergence performances. However, given that the FGAP can be often affected by uncertainty or approximation in data, in this paper we develop a new metaheuristic algorithm, based on the Fuzzy Bee Colony Optimization (FBCO), which integrates the concepts of BCO with a Fuzzy Inference System. The proposed method assigns, through the multicriteria analysis, airport gates to scheduled flights based on both passengers’ total walking distance and use of remote gates, to find an optimal flight-to-gate assignment for a given schedule. Comparison of the results with the schedules of real airports has allowed us to show the characteristics of the proposed concepts and, at the same time, it stressed the effectiveness of the proposed method.     

Counting the different efficient paths for transportation networks and its applications

This paper deals with an interesting problem about how to efficiently compute the number of different efficient paths between an origin‐destination pair for a transportation network because these efficient paths are the possible paths used by drivers to some extent. Based on a novel triangle operation derived, it first presents a polynomial‐time combinatorial algorithm that can obtain the number of different simple paths between any two nodes for an acyclic network as well as the total travel cost of these paths. This paper proceeds to develop a combinatorial algorithm with polynomial‐time complexity for both counting the different efficient paths between an origin‐destination pair and calculating the total travel cost of these paths. As for applications, this paper shows that the preceding two algorithms can yield the lower and upper bounds for the number of different simple paths between an origin‐destination pair, while it has already be recognized that a polynomial‐time algorithm getting such a number does not exist for a general network. Furthermore, the latter algorithm can be applied for developing a heuristic method for the traffic counting location problem arising from the origin‐destination matrix estimation problems.     

A continuous approximation model for time definite many-to-many transportation

Time definite freight transportation carriers provide very reliable scheduled services between origin and destination terminals. They seek to reduce transportation costs through consolidation of shipments at hubs, but are restricted by the high levels of service to provide less circuitous routings. This paper develops a continuous approximation model for time definite transportation from many origins to many destinations. We consider a transportation carrier serving a fixed geographic region in which demand is modeled as a continuous distribution and time definite service levels are imposed by limiting the maximum travel distance via the hub network. Analytical expressions are developed for the optimal number of hubs, hub locations, and transportation costs. Computational results for an analogous discrete demand model are presented to illustrate the behavior observed with the continuous approximation models.     

The vehicle platooning problem: Computational complexity and heuristics

We create a mathematical framework for modeling trucks traveling in road networks, and we define a routing problem called the platooning problem. We prove that this problem is NP-hard, even when the graph used to represent the road network is planar. We present integer linear programming formulations for instances of the platooning problem where deadlines are discarded, which we call the unlimited platooning problem. These allow us to calculate fuel-optimal solutions to the platooning problem for large-scale, real-world examples. The problems solved are orders of magnitude larger than problems previously solved exactly in the literature. We present several heuristics and compare their performance with the optimal solutions on the German Autobahn road network. The proposed heuristics find optimal or near-optimal solutions in most of the problem instances considered, especially when a final local search is applied. Assuming a fuel reduction factor of 10% from platooning, we find fuel savings from platooning of 1–2% for as few as 10 trucks in the road network; the percentage of savings increases with the number of trucks. If all trucks start at the same point, savings of up to 9% are obtained for only 200 trucks.     

Pre-timed control for an under-saturated and over-saturated isolated intersection: a Bee Colony Optimization approach

In this paper we study the problem of determining the optimum cycle and phase lengths for isolated signalized intersections. Calculation of the optimal cycle and green phase lengths is based on the minimization of the average control delay experienced by all vehicles that arrive at the intersection within a given time period. We consider under-saturated as well as over-saturated conditions at isolated intersections. The defined traffic signal timing problem, that belongs to the class of combinatorial optimization problems, is solved using the Bee Colony Optimization (BCO) metaheuristic approach. The BCO is a biologically inspired method that explores collective intelligence applied by honey bees during the nectar collecting process. The numerical experiments performed on some examples show that the proposed approach is competitive with other methods. The obtained results show that the proposed approach is capable of generating high-quality solutions within negligible processing times.     

Transportation service procurement problem with transit time

In this work, we investigate transit time in transportation service procurement, which is conducted by shippers using auctions to purchase transportation service from carriers in the planning stage. Besides cost, we find that many shippers are most concerned with transit time in practice; shorter transit time indicates better transportation service. To minimize both the total cost and transit time, the problem faced by shippers is the biobjective transportation service procurement problem with transit time. To solve the problem, we introduce a biobjective integer programming model that can also accommodate some important business constraints. A biobjective branch-and-bound algorithm that finds all extreme supported nondominated solutions is developed. To speed up the algorithm, two fast feasibility checks, a network flow model for particular subproblems, and lower bounds from relaxation are proposed. In addition, a sophisticated heuristic is introduced to meet shipper’s requirements in some situations. Computational experiments on evaluating the performance of the algorithms are conducted on a set of test instances that are generated from practical data.     

Approximate algorithms for the discrete network design problem

The discrete network design problem is one of finding a set of feasible actions (projects) from among a collection of possible actions, that when implemented, optimizes some objective function(s). This is a combinatorial optimization problem that is very expensive to solve exactly. This paper proposes two algorithms for obtaining approximate solutions to the discrete network design problem with much less computational effeort. The computational savings are achieved by approximating the original problem with a new formulation which is easier to solve. The first algorithm proposed solves this approximate problem exactly, while the second is even more efficient, but provides only a near-optimal solution to the approximate problem. Experience with test problems indicates that these approximations can reduce the computational effort by a factor of 3–5, with little loss in solution accuracy.     

How to restrain participants opt out in shared parking market? A fair recurrent double auction approach

We propose a fair recurrent double VCG (FRD-VCG) auction mechanism to approach the emerging shared parking management problem. In a given shared parking environment with a parking management platform and a double-side perspective, the proposed mechanism considers how to restrain the potential participants (parking slot demanders and slot suppliers) opt out, which is based on the participants’ priority attributes and are calculated with respect to historic auction records provided by the parking platform. Participants’ fairness bids are then generated combining their priority attributes and their submitted bids (bid price and parking time) with the support of a novel evaluation function, which integrates priority attributes, bid price and parking time into an output value. The parking slot allocation rule and transaction payment rule are further designed to dealing with these issues include winner determination and price setting, respectively. Simulations show advantages of the proposed FRD-VCG mechanism, i.e., comparing with the double VCG (D-VCG) mechanism for the shared parking management problem where priority attributes and evaluation function are not considered, the proposed FRD-VCG mechanism has the potential to persuade participants to remain in the market whilst it improves the market’s retention rate, the parking slot’s utilization rate and the participants’ utilities.     

A steady-state solution for the optimal pavement resurfacing problem

This paper presents a solution approach for the problem of optimising the frequency and intensity of pavement resurfacing, under steady-state conditions. If the pavement deterioration and improvement models are deterministic and follow the Markov property, it is possible to develop a simple but exact solution method. This method removes the need to solve the problem as an optimal control problem, which had been the focus of previous research in this area. The key to our approach is the realisation that, at optimality, the system enters the steady state at the time of the first resurfacing. The optimal resurfacing strategy is to define a minimum serviceability level (or maximum roughness level), and whenever the pavement deteriorates to that level, to resurface with a fixed intensity. The optimal strategy does not depend on the initial condition of the pavement, as long as the initial condition is better than the condition that triggers resurfacing. This observation allows us to use a simple solution method. We apply this solution procedure to a case study, using data obtained from the literature. The results indicate that the discounted lifetime cost is not very sensitive to cycle time. What matters most is the best achievable roughness level. The minimum serviceability level strategy is robust in that when there is uncertainty in the deterioration process, the optimal condition that triggers resurfacing is not significantly changed.     

Multiple criteria optimization method for the vehicle assignment problem in a bus transportation company

A vehicle assignment problem (VAP) in a road, long‐haul, passenger transportation company with heterogeneous fleet of buses is considered in the paper. The mathematical model of the VAP is formulated in terms of multiobjective, combinatorial optimization. It has a strategic, long‐term character and takes into account four criteria that represent interests of both passengers and the company's management. The decision consists in the definition of weekly operating frequency (number of rides per week) of buses on international routes between Polish and Western European cities. The VAP is solved in a step‐wise procedure. In the first step a sample of efficient (Pareto‐optimal) solutions is generated using an original metaheuristic method called Pareto Memetic Algorithm (PMA). In the second step this sample is reviewed and evaluated by the Decision Maker (DM). In this phase an interactive, multiple criteria analysis method with graphical facilities, called Light Beam Search (LBS), is applied. The method helps the DM to define his/her preferences, direct the search process and select the most satisfactory solution.     

Dynamic pricing for managed lanes with multiple entrances and exits

Priced managed lanes are increasingly being used to better utilize the existing capacity of the roadway to relieve congestion and offer reliable travel time to road users. In this paper, we investigate the optimization problem for pricing managed lanes with multiple entrances and exits which seeks to maximize the revenue and minimize the total system travel time (TSTT) over a finite horizon. We propose a lane choice model where travelers make online decisions at each diverge point considering all routes on a managed lane network. We formulate the problem as a deterministic Markov decision process and solve it using the value function approximation (VFA) method for different initializations. We compare the performance of the toll policies predicted by the VFA method against the myopic revenue policy which maximizes the revenue only at the current timestep and two heuristic policies based on the measured densities on the managed and general purpose lanes (GPLs). We test the results on four different test networks. The primary findings from our research suggest the usefulness of the VFA method for determining dynamic tolls. The best-found objective value from the method at its termination is better than other heuristics for all test networks with average improvements in the objective ranging between 10% and 90% for revenue maximization and 0–27% for TSTT minimization. Certain VFA initializations obtain best-found toll profiles within first 5–50 iterations which warrants computational time savings. Our findings also indicate that the revenue-maximizing optimal policies follow the “jam-and-harvest” behavior where the GPLs are pushed towards congestion in the earlier time steps to generate higher revenue in the later time steps, a characteristic not observed for the policies minimizing TSTT.     

A joint optimization model for liner container cargo assignment problem using state-augmented shipping network framework

This paper proposes a state-augmented shipping (SAS) network framework to integrate various activities in liner container shipping chain, including container loading/unloading, transshipment, dwelling at visited ports, in-transit waiting and in-sea transport process. Based on the SAS network framework, we develop a chance-constrained optimization model for a joint cargo assignment problem. The model attempts to maximize the carrier’s profit by simultaneously determining optimal ship fleet capacity setting, ship route schedules and cargo allocation scheme. With a few disparities from previous studies, we take into account two differentiated container demands: deterministic contracted basis demand received from large manufacturers and uncertain spot demand collected from the spot market. The economies of scale of ship size are incorporated to examine the scaling effect of ship capacity setting in the cargo assignment problem. Meanwhile, the schedule coordination strategy is introduced to measure the in-transit waiting time and resultant storage cost. Through two numerical studies, it is demonstrated that the proposed chance-constrained joint optimization model can characterize the impact of carrier’s risk preference on decisions of the container cargo assignment. Moreover, considering the scaling effect of large ships can alleviate the concern of cargo overload rejection and consequently help carriers make more promising ship deployment schemes.     

双层保温层经济厚度的优化计算

通过对双层保温的总费用分析，并考虑到保温的国家标准和工程实际，建立了双层保温层经济厚度优化设计的数学模型，并采用最优化方法进行了编程求解，得到了每层的最佳经济厚度。导出的模型和编制的软件可帮助设计人员合理地选择保温材料并确定其经济厚度，有助于提高设计效率和设计质量。