•A mixed integer non linear programming model on ship routing and deployment is proposed.•Some important properties of the proposed problem are obtained.•A dynamic programming based method is ...developed.•The proposed model can contribute to cost savings.
This paper addresses a joint ship path, speed, and deployment problem in a liner shipping company considering three emission reduction measures, including sulfur emission regulations, carbon tax, and vessel speed reduction incentive programs (VSRIPs). Given a set of service routes and the total number of available ships, the proposed problem determines how many ships should be deployed on each route and how to design sailing path and speed for each leg. A mixed-integer non-linear programming model is presented for minimizing the total cost of all routes, i.e., fuel cost, carbon tax, and fixed cost, minus dockage refund. The different impacts of the three emission reduction measures on sailing path and speed complicate the problem. Some important properties are obtained by analyzing the proposed model. Combining these properties with a dynamic programming approach, a tailored method is developed to solve the problem. Based on real data, extensive numerical experiments are conducted to examine the validity of the proposed model and the efficiency of the solution method. The computational results demonstrate that the proposed model can contribute to significant cost savings for shipping companies.
•We address the optimal location of multiple types of BEV charging facilities, including dynamic wireless charging facilities and different levels of plug-in charging stations.•A tri-level ...programming is developed to model the presented problem.•An efficient solution algorithm is proposed to solve the model, wherein the formulated model is first treated as a black-box optimization, and then solved by an efficient surface response approximation model based solution algorithm.
To reduce greenhouse gas emissions in transportation sector, battery electric vehicle (BEV) is a better choice towards the ultimate goal of zero-emission. However, the shortened range, extended recharging time and insufficient charging facilities hinder the wide adoption of BEV. Recently, a wireless power transfer technology, which can provide dynamic recharging when vehicles are moving on roadway, has the potential to solve these problems. The dynamic recharging facilities, if widely applied on road network, can allow travelers to drive in unlimited range without stopping to recharge. This paper aims to study the complex charging facilities location problem, assuming the wireless charging is technologically mature and a new type of wireless recharging BEV is available to be selected by consumers in the future other than the traditional BEV requiring fixed and static charging stations. The objective is to assist the government planners on optimally locating multiple types of BEV recharging facilities to satisfy the need of different BEV types within a given budget to minimize the public social cost. Road users’ ownership choice among multiple types BEV and BEV drivers’ routing choice behavior are both explicitly considered. A tri-level programming is then developed to model the presented problem. The formulated model is first treated as a black-box optimization, and then solved by an efficient surface response approximation model based solution algorithm.
•We introduce a dynamic pricing strategy with negative prices into bike sharing systems.•This is the first study to deal with the bike relocation or bike repositioning problem using user-based ...approach in dockless bike sharing system.•A dynamic traffic assignment model and its solution algorithm are developed to capture travellers’ mode-path choice behaviour in response to the proposed dynamic pricing strategy.•A systematic comparison among the traditional positive price strategy, free price strategy and the proposed strategy is analysed.
To achieve bike relocation11The bike relocation mentioned in this paper is also referred as bike repositioning in the literature. through travellers’ spontaneous behaviour in dockless bike sharing systems, an innovative dynamic pricing scheme with negative prices is introduced. In normal situation, users pay a positive price to operators for using a bike. However, when imbalanced distribution of bikes occurs in the system, users who cycle from the oversupplied area to undersupplied area will receive monetary reward from the operator, i.e., negative pricing applies. A user equilibrium dynamic traffic assignment model is developed to capture travellers’ mode-path choice behaviour in response to the proposed dynamic pricing strategy. Travellers can either use a single transportation mode (e.g. walking, cycling and bus) or take multiple modes to complete their trips. The user equilibrium travel pattern is formulated as a variational inequality problem and then solved by a path-flow swapping algorithm. Two numerical examples are conducted to demonstrate that the proposed dynamic pricing strategy with negative prices is effective in terms of attracting users as well as achieving a more balanced bike repositioning, especially when the number of bikes provided in the system is limited.
The road network design problem, typically formulated as a bi-level program or a mathematical program with equilibrium constraints, is generally non-convex. The non-convexity stems from both the ...traffic assignment equilibrium conditions and the non-linear travel time function. In this study, we formulate the network design problem as a single-level optimization problem with equilibrium constraints, and then we transform the equilibrium constraints into a set of mixed-integer constraints and linearize the travel time function. The final result is that we cast the network design problem with equilibrium flows into a mixed-integer linear program, whose solution possesses the desirable property of global optimality, subject to the resolution of the linearization scheme adopted.
•Continuous network design problem with stochastic user equilibrium is explored.•The problem is reformulated as a nonlinear nonconvex programming.•A tight mixed-integer linear programming relaxation ...is derived.•A global optimization method based on range reduction technique is proposed.
In this paper, we consider the continuous road network design problem with stochastic user equilibrium constraint that aims to optimize the network performance via road capacity expansion. The network flow pattern is subject to stochastic user equilibrium, specifically, the logit route choice model. The resulting formulation, a nonlinear nonconvex programming problem, is firstly transformed into a nonlinear program with only logarithmic functions as nonlinear terms, for which a tight linear programming relaxation is derived by using an outer-approximation technique. The linear programming relaxation is then embedded within a global optimization solution algorithm based on range reduction technique, and the proposed approach is proved to converge to a global optimum.
•A novel discrete transportation network design problem formulation is developed.•It is a general model and includes conventional CNDP and DNDP as particular cases.•A global optimization solution ...method is developed to solve the problem.•The solution approach converges to the exact global optimum solutions.
Conventional discrete transportation network design problem deals with the optimal decision on new link addition, assuming the capacity of each candidate link addition is predetermined and fixed. In this paper, we address a novel yet general discrete network design problem formulation that aims to determine the optimal new link addition and their optimal capacities simultaneously, which answers the questions on whether a new link should be added or not, and if added, what should be the optimal link capacity. A global optimization method employing linearization, outer approximation and range reduction techniques is developed to solve the formulated model.
•We study a continuous transit network problem with explicit consideration of congested common lines.•The problem is formulated into a tri-level programming model.•We propose two solution methods to ...solve the proposed model. One is to transform the model into a mixed-integer linear programming (MILP). The other is the surrogate optimization based method.•We perform extensive numerical studies to test the proposed model formulation and solution methods.
This paper focuses on a transit service operation design problem that primarily determines the optimal frequency settings with explicit consideration of congested common lines in a bus service network. Other than passengers’ transit route choices, the transit service line choices among congested common lines are also specified in the model formulation. A tri-level programming approach is applied to formulate this problem, wherein the upper-level program optimizes the transit frequency to minimize the total operating costs and passengers’ transit costs; the middle-level program describes passengers’ transit routing choices, in which passengers will select a sequence of transfer nodes to minimize their transit costs; and the lower-level program formulates the equilibrium strategy in the common line problem on the route sections (i.e., between two successive transfer nodes), whose equilibrium solution may have multiple strategies depending on the congestion level of the common lines. The tri-level model is then reformulated into a mathematical program with equilibrium constraints. Two solution methods are proposed to solve the problem. One is to transform the model into a mixed-integer linear program so that the global optimal solution of the linearized problem can be guaranteed, and the other employs a surrogate optimization approach to ensure high solution efficiency for large size problems without compromising solution quality. Finally, we conduct extensive numerical examples to demonstrate the validity of our model formulation and the performance of the proposed solution algorithms.
The emerging technology of autonomous vehicles has been widely recognized as a promising urban mobility solution in the future. This paper considers the integration of autonomous vehicles into bus ...transit systems and proposes a modeling framework to determine the optimal bus fleet size and its assignment onto multiple bus lines in a bus service network considering uncertain demand. The mixed-integer stochastic programming approach is applied to formulate the problem. We apply the sample average approximation (SAA) method to solve the formulated stochastic programming problem. To tackle the nonconvexity of the SAA problem, we first present a reformulation method that transforms the problem into a mixed-integer conic quadratic program (MICQP), which can be solved to its global optimal solution by using some existing solution methods. However, this MICQP based approach can only handle the small-size problems. For the cases with large problem size, we apply the approach of quadratic transform with linear alternating algorithm, which allows for efficient solution to large-scale instances with up to thousands of scenarios in a reasonable computational time. Numerical results demonstrate the benefits of introducing autonomous buses as they are flexible to be assigned across different bus service lines, especially when demand uncertainty is more significant. The introduction of autonomous buses would enable further reduction of the required fleets and total cost. The model formulation and solution methods proposed in this study can be used to provide bus transit operators with operational guidance on including autonomous buses into bus services, especially on the autonomous and conventional bus fleets composition and allocation.
•We model and solve the spatial equilibrium travel pattern in a linear travel corridor with continuous P&R facilities.•Heterogeneous commuters and travel time reliability are considered in model ...formulation.•Linear complementarity system approach is applied in model formulation.•Proof of solution existence of the model is provided.•Potential model applications are demonstrated.
This paper studies the modeling of multimodal choice in a highway/railway system with continuum park-and-ride services along a corridor. Commuter heterogeneity and travel time uncertainty with correlation are considered, while both auto and rail transit are subject to congestion effects. Eventually, the equilibrium multimodal choice is modeled into a linear complementarity system and appropriate solution method is proposed to obtain the spatial equilibrium pattern along the corridor. Computational experiments are conducted to demonstrate the benefits of the proposed formulation and potential applications, such as optimization of park-and-ride facilities, development of land use policies to integrate urban development and transportation planning.
The new generation of bicycle-sharing is an O2O (online-to-offline) platform service that enables the users to access the bicycle with a smartphone App. This paper proposes a dynamic repositioning ...model with predicted demand, where the repositioning time interval is fixed. A data-driven Neural Network (NN) approach is introduced to forecast the bicycle-sharing demand. The repositioning objective function at each time interval is defined to simultaneously minimize the operator cost and penalty cost. In addition to the normal constraints in static repositioning problem, flow conservation, inventory-balance and travel time constraints are taken into account. Due to the non-deterministic polynomial-time hard (NP-hard) nature of this model, a hybrid metaheuristic approach of Adaptive Genetic Algorithm (AGA) and Granular Tabu Search (GTS) algorithm is applied to calculate the solution. Based on predicted demand, the initial repositioning plan is made by AGA statically at the beginning of study horizon, which ensures the global optimization of the first solution. As time goes on, repositioning plan is checked and updated according to the real-usage patterns using GTS algorithm, which has the advantage of high-performance local-search within a short computing time. Numerical analysis is conducted using the real cases. The simulation results reveal that the proposed methodology can effectively model the dynamic repositioning problem in response to real-time bicycle-sharing usage. The proposed methodology can be a value-added tool in enhancing the feasibility and sustainability of bicycle-sharing program.
PDF
