A static free-floating bike repositioning problem with multiple heterogeneous vehicles,multiple depots,and multiple visits

In this paper, a bike repositioning problem with multiple depots, multiple visits, and multiple heterogeneous vehicles for the free-floating bike-sharing system (FFBSS) is studied. Two types of nodes (i.e., easily and hardly access nodes) with different penalties are defined to represent different convenience levels of getting bikes from the FFBSS. The objective of the repositioning is to minimize the weighted sum of the inconvenience level of getting bikes from the system and the total unmet demand and the total operational time. To solve this problem, an enhanced version of chemical reaction optimization (CRO) is developed. A loading and unloading quantity adjustment procedure with the consideration of the node characteristics, including the type of node and its current state (i.e., in a balanced, surplus, or deficit state) is proposed and incorporated into this version to improve its solution quality. A concept of the nearby-node set is also proposed to narrow the search space. Numerical results are presented and indicate that compared to the traditional CRO and CPLEX, the enhanced CRO improves solution quality and has potential to tackle the repositioning problem for larger, longer repositioning duration, and more vehicle instances. The results also demonstrate the effectiveness of the proposed adjustment procedure.     

Dynamic green bike repositioning problem – A hybrid rolling horizon artificial bee colony algorithm approach

This paper introduces a new dynamic green bike repositioning problem (DGBRP) that simultaneously minimizes the total unmet demand of the bike-sharing system and the fuel and CO₂ emission cost of the repositioning vehicle over an operational period. The problem determines the route and the number of bikes loaded and unloaded at each visited node over a multi-period operational horizon during which the cycling demand at each node varies from time to time. To handle the dynamic nature of the problem, this study adopts a rolling horizon approach to break down the proposed problem into a set of stages, in which a static bike repositioning sub-problem is solved in each stage. An enhanced artificial bee colony (EABC) algorithm and a route truncation heuristic are jointly used to optimize the route design in each stage, and the loading and unloading heuristic is used to tackle the loading and unloading sub-problem along the route in a given stage. Numerical results show that the EABC algorithm outperforms Genetic Algorithm in solving the routing sub-problem. Computation experiments are performed to illustrate the effect of the stage duration on the two objective values, and the results show that longer stage duration leads to higher total unmet demand and total fuel and CO₂ emission cost. Numerical studies are also performed to illustrate the effects of the weight and the loading and unloading times on the two objective values and the tradeoff between the two objectives.     

Free-floating bike sharing: Solving real-life large-scale static rebalancing problems

Free-floating bike sharing (FFBS) is an innovative bike sharing model. FFBS saves on start-up cost, in comparison to station-based bike sharing (SBBS), by avoiding construction of expensive docking stations and kiosk machines. FFBS prevents bike theft and offers significant opportunities for smart management by tracking bikes in real-time with built-in GPS. However, like SBBS, the success of FFBS depends on the efficiency of its rebalancing operations to serve the maximal demand as possible.Bicycle rebalancing refers to the reestablishment of the number of bikes at sites to desired quantities by using a fleet of vehicles transporting the bicycles. Static rebalancing for SBBS is a challenging combinatorial optimization problem. FFBS takes it a step further, with an increase in the scale of the problem. This article is the first effort in a series of studies of FFBS planning and management, tackling static rebalancing with single and multiple vehicles. We present a Novel Mixed Integer Linear Program for solving the Static Complete Rebalancing Problem. The proposed formulation, can not only handle single as well as multiple vehicles, but also allows for multiple visits to a node by the same vehicle. We present a hybrid nested large neighborhood search with variable neighborhood descent algorithm, which is both effective and efficient in solving static complete rebalancing problems for large-scale bike sharing programs.Computational experiments were carried out on the 1 Commodity Pickup and Delivery Traveling Salesman Problem (1-PDTSP) instances used previously in the literature and on three new sets of instances, two (one real-life and one general) based on Share-A-Bull Bikes (SABB) FFBS program recently launched at the Tampa campus of University of South Florida and the other based on Divvy SBBS in Chicago. Computational experiments on the 1-PDTSP instances demonstrate that the proposed algorithm outperforms a tabu search algorithm and is highly competitive with exact algorithms previously reported in the literature for solving static rebalancing problems in SBSS. Computational experiments on the SABB and Divvy instances, demonstrate that the proposed algorithm is able to deal with the increase in scale of the static rebalancing problem pertaining to both FFBS and SBBS, while deriving high-quality solutions in a reasonable amount of CPU time.     

Vehicle sharing system with fleet sizing and multi-transportation modes under allowable shortages: a hybrid metaheuristic approach

In this paper, a vehicle sharing system with multi-transportation modes and allowable shortage is presented. This model aims to minimize the system's total cost by using optimum locations and number of stations, routes, transportation modes, station capacities for different modes and time between stations balancing. Because of the model's complexity, currently available proprietary software is not able to solve the model in a reasonable computational time, so a hybrid algorithm based on a genetic algorithm (GA) and particle swarm optimization is presented. The results confirm its efficiency compared with the classic GA and exact solution methods. Moreover, a sensitivity analysis shows the applicability of the proposed algorithm.     

A model for the layout of bike stations in public bike‐sharing systems

The problem of designing a layout of bike stations for public bike‐sharing systems entails selecting a number of stations and then constructing them within a planning area having many bike traffic zones and candidate bike stations. In this paper, we proposed a mathematical model to formulate the layout of public bike stations with the objective of minimizing users' total travel time and investment budget constraints. The model can guarantee that the needs for picking up and dropping off bikes amidst all bike travel demands are satisfied. Using this model, the number and locations of bike stations and the number of bikes and parking lockers at each bike station can be simultaneously determined. A typical example solved by lingo solver is created to illustrate the proposed model. Copyright © 2015 John Wiley & Sons, Ltd.     

A bi-level model for single-line rail timetable design with consideration of demand and capacity

This paper proposes a bi-level model to solve the timetable design problem for an urban rail line. The upper level model aims at determining the headways between trains to minimize total passenger cost, which includes not only the usual perceived travel time cost, but also penalties during travel. With the headways given by the upper level model, passengers’ arrival times at their origin stops are determined by the lower level model, in which the cost-minimizing behavior of each passenger is taken into account. To make the model more realistic, explicit capacity constraints of individual trains are considered. With these constraints, passengers cannot board a full train, but wait in queues for the next coming train. A two-stage genetic algorithm incorporating the method of successive averages is introduced to solve the bi-level model. Two hypothetical examples and a real world case are employed to evaluate the effectiveness of the proposed bi-level model and algorithm. Results show that the bi-level model performs well in reducing total passenger cost, especially in reducing waiting time cost and penalties. And the section loading-rates of trains in the optimized timetable are more balanced than the even-headway timetable. The sensitivity analyses show that passenger’s desired arrival time interval at destination and crowding penalty factor have a high influence on the optimal solution. And with the dispersing of passengers' desired arrival time intervals or the increase of crowding penalty factor, the section loading-rates of trains become more balanced.     

Optimal timetable development for community shuttle network with metro stations

This paper investigates an issue for optimizing synchronized timetable for community shuttles linked with metro service. Considering a passenger arrival distribution, the problem is formulated to optimize timetables for multiple community shuttle routes, with the objective of minimizing passenger’s schedule delay cost and transfer cost. Two constraints, i.e., vehicle capacity and fleet size, are modeled in this paper. The first constraint is treated as soft, and the latter one is handled by a proposed timetable generating method. Two algorithms are employed to solve the problem, i.e., a genetic algorithm (GA) and a Frank–Wolfe algorithm combined with a heuristic algorithm of shifting departure times (FW-SDT). FW-SDT is an algorithm specially designed for this problem. The simulated and real-life examples confirm the feasibility of the two algorithms, and demonstrate that FW-SDT outperforms GA in both accuracy and effectiveness.     

Chemical reaction optimization for solving a static bike repositioning problem

In this paper, the single-vehicle static repositioning problem is studied. The objective of repositioning is to minimize the weighted sum of unmet customer demand and operational time on the vehicle route. To solve this problem, chemical reaction optimization (CRO) is proposed to handle the vehicle routes, and a subroutine is proposed to determine the loading and unloading quantities at each visited station. An enhanced version of CRO is proposed to improve the solution quality of the original CRO by adding new operators, rules, and intensive neighbor solution search methods. The concept of a neighbor-node set is proposed to narrow the solution search space. To illustrate the efficiency and accuracy of the enhanced CRO, different test scenarios are set and the results obtained from IBM ILOG CPLEX, the original CRO, and the enhanced CRO are compared. The computational results indicate that the enhanced CRO provides high-quality solutions with shorter computing times than those of IBM ILOG CPLEX and provides better solutions than the original CRO. The results also demonstrate that incorporation of the two neighbor-node sets into the enhanced CRO improves the solution quality, and the probability of running the intensive search should increase with iteration in the final part of the main stage of the algorithm to obtain better solutions.     

A hybrid Genetic Algorithm approach to minimize the total joint cost of a single-vendor multi-customer integrated scheduling problem

This paper addresses the scheduling of supply chains with interrelated factories consisting of a single vendor and multiple customers. In this research, one transporter is available to deliver jobs from vendor to customers, and the jobs can be processed by batch. The problem studied in this paper focuses on a real-case scheduling problem of a multi-location hospital supplied with a central pharmacy. The objective of this work is to minimize the total cost, while satisfying the customer’s due dates constraints. A mathematical formulation of the problem is given as a Mixed Integer Programming model. Then, a Branch-and-Bound algorithm is proposed as an exact method for solving this problem, a greedy local search is developed as a heuristic approach, and a hybrid Genetic Algorithm is presented as a meta-heuristic. Computation experiments are conducted to highlight the performance of the proposed methods.     

The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace

The integration of drones into civil airspace is one of the most challenging problems for the automation of the controlled airspace, and the optimization of the drone route is a key step for this process. In this paper, we optimize the route planning of a drone mission that consists of departing from an airport, flying over a set of mission way points and coming back to the initial airport. We assume that during the mission a set of piloted aircraft flies in the same airspace and thus the cost of the drone route depends on the air traffic and on the avoidance maneuvers used to prevent possible conflicts. Two air traffic management techniques, i.e., routing and holding, are modeled in order to maintain a minimum separation between the drone and the piloted aircraft. The considered problem, called the Time Dependent Traveling Salesman Planning Problem in Controlled Airspace (TDTSPPCA), relates to the drone route planning phase and aims to minimize the total operational cost. Two heuristic algorithms are proposed for the solution of the problem. A mathematical formulation based on a particular version of the Time Dependent Traveling Salesman Problem, which allows holdings at mission way points, and a Branch and Cut algorithm are proposed for solving the TDTSPPCA to optimality. An additional formulation, based on a Travelling Salesman Problem variant that uses specific penalties to model the holding times, is proposed and a Cutting Plane algorithm is designed. Finally, computational experiments on real-world air traffic data from Milano Linate Terminal Maneuvering Area are reported to evaluate the performance of the proposed formulations and of the heuristic algorithms.     

Intermodal hub-and-spoke network design: Incorporating multiple stakeholders and multi-type containers

This paper develops a mathematical program with equilibrium constraints (MPEC) model for the intermodal hub-and-spoke network design (IHSND) problem with multiple stakeholders and multi-type containers. The model incorporates a parametric variational inequality (VI) that formulates the user equilibrium (UE) behavior of intermodal operators in route choice for any given network design decision of the network planner. The model also uses a cost function that is capable of reflecting the transition from scale economies to scale diseconomies in distinct flow regimes for carriers or hub operators, and a disutility function integrating actual transportation charges and congestion impacts for intermodal operators. To solve the MPEC model, a hybrid genetic algorithm (HGA) embedded with a diagonalization method for solving the parametric VI is proposed. Finally, the comparative analysis of the HGA and an exhaustive enumeration algorithm indicates a good performance of the HGA in terms of computational time and solution quality. The HGA is also applied to solve a large-scale problem to show the applicability of the proposed model and algorithm.     

The Hybrid Vehicle Routing Problem

In this paper the Hybrid Vehicle Routing Problem (HVRP) is introduced and formalized. This problem is an extension of the classical VRP in which vehicles can work both electrically and with traditional fuel. The vehicle may change propulsion mode at any point of time. The unitary travel cost is much lower for distances covered in the electric mode. An electric battery has a limited capacity and may be recharged at a recharging station (RS). A limited number of RS are available. Once a battery has been completely discharged, the vehicle automatically shifts to traditional fuel propulsion mode. Furthermore, a maximum route duration is imposed according to contracts regulations established with the driver. In this paper, a Mixed Integer Linear Programming formulation is presented and a Large Neighborhood Search based Matheuristic is proposed. The algorithm starts from a feasible solution and consists into destroying, at each iteration, a small number of routes, letting unvaried the other ones, and reconstructing a new feasible solution running the model on only the subset of customers involved in the destroyed routes. This procedure allows to completely explore a large neighborhood within very short computational time. Computational tests that show the performance of the matheuristic are presented. The method has also been tested on a simplified version of the HVRP already presented in the literature, the Green Vehicle Routing Problem (GVRP), and competitive results have been obtained.     

The dynamic shortest path problem with time-dependent stochastic disruptions

The dynamic shortest path problem with time-dependent stochastic disruptions consists of finding a route with a minimum expected travel time from an origin to a destination using both historical and real-time information. The problem is formulated as a discrete time finite horizon Markov decision process and it is solved by a hybrid Approximate Dynamic Programming (ADP) algorithm with a clustering approach using a deterministic lookahead policy and value function approximation. The algorithm is tested on a number of network configurations which represent different network sizes and disruption levels. Computational results reveal that the proposed hybrid ADP algorithm provides high quality solutions with a reduced computational effort.     

Promoting public bike-sharing: A lesson from the unsuccessful Pronto system

In 2014, Seattle implemented its own bike-sharing system, Pronto. However, the system ultimately ceased operation three years later on March 17th, 2017. To learn from this failure, this paper seeks to understand factors that encourage, or discourage, bike-sharing trip generation and attraction at the station level. This paper investigates the effects of land use, roadway design, elevation, bus trips, weather, and temporal factors on three-hour long bike pickups and returns at each docking station. To address temporal autocorrelations and the nonlinear seasonality, the paper implements a generalized additive mixed model (GAMM) that incorporates the joint effects of a time metric and time-varying variables. The paper estimates models on total counts of pickups and returns, as well as pickups categorized by user types and by location. The results clarify that effects of hilly terrain and the rainy weather, two commonly perceived contributors to the failure. Additionally, results suggest that users in the University District, presumably mostly university students, tend to use shared bikes in neighborhoods with a higher household density and a higher percentage of residential land use, and make bike-sharing trips regardless workdays or non-workdays. The paper also contributes to the discussion on the relationship between public transportation service and bike-sharing. In general, users tend to use bike-sharing more at stations that have more scheduled bus trips nearby. However, some bike-sharing users may shift to bus services during peak hours and rainy weather. Several strategies are proposed accordingly to increase bike ridership in the future.     

Evolutionary crew scheduling with adaptive chromosomes

This paper presents an adaptive evolutionary approach incorporating a hybrid genetic algorithm (GA) for public transport crew scheduling problems, which are well-known to be NP-hard. To ensure the search efficiency, a suitable chromosome representation has to be determined first. Unlike a canonical GA for crew scheduling where the chromosome length is fixed, the chromosome length in the proposed approach may vary adaptively during the iterative process, and its initial value is elaborately designated as the lower bound of the number of shifts to be used in an unachievable optimal solution. Next, the hybrid GA with such a short chromosome length is employed to find a feasible schedule. During the GA process, the adaptation on chromosome lengths is achieved by genetic operations of crossover and mutation with removal and replenishment strategies aided by a simple greedy algorithm. If a feasible schedule cannot be found when the GA’s termination condition is met, the GA will restart with one more gene added. The above process is repeated until a feasible solution is found. Computational experiments based on 11 real-world crew scheduling problems in China show that, compared to a fuzzy GA known to be well performed for crew scheduling, better solutions are found for all the testing problems. Moreover, the algorithm works fast, has achieved results close to the lower bounds obtained by a standard linear programming solver in terms of the number of shifts, and has much potential for future developments.     

Transport Network Design Problem under Uncertainty: A Review and New Developments

This paper aims to provide a state-of-the-art review of the transport network design problem (NDP) under uncertainty and to present some new developments on a bi-objective-reliable NDP (BORNDP) model that explicitly optimizes the capacity reliability and travel time reliability under demand uncertainty. Both are useful performance measures that can describe the supply-side reliability and demand-side reliability of a road network. A simulation-based multi-objective genetic algorithm solution procedure, which consists of a traffic assignment algorithm, a genetic algorithm, a Pareto filter, and a Monte-Carlo simulation, is developed to solve the proposed BORNDP model. A numerical example based on the capacity enhancement problem is presented to demonstrate the tradeoff between capacity reliability and travel time reliability in the NDP.     

Adding a new station and a road link to a road–rail network in the presence of modal competition

In this paper we study the problem of locating a new station on an existing rail corridor and a new junction on an existing road network, and connecting them with a new road segment under a budget constraint. We consider three objective functions and the corresponding optimization problems, which are modeled by means of mixed integer non-linear programs. For small instances, the models can be solved directly by a standard solver. For large instances, an enumerative algorithm based on a discretization of the problem is proposed. Computational experiments show that the latter approach yields high quality solutions within short computing times.     

Joint inventory-location problem under the risk of probabilistic facility disruptions

This paper studies a reliable joint inventory-location problem that optimizes facility locations, customer allocations, and inventory management decisions when facilities are subject to disruption risks (e.g., due to natural or man-made hazards). When a facility fails, its customers may be reassigned to other operational facilities in order to avoid the high penalty costs associated with losing service. We propose an integer programming model that minimizes the sum of facility construction costs, expected inventory holding costs and expected customer costs under normal and failure scenarios. We develop a Lagrangian relaxation solution framework for this problem, including a polynomial-time exact algorithm for the relaxed nonlinear subproblems. Numerical experiment results show that this proposed model is capable of providing a near-optimum solution within a short computation time. Managerial insights on the optimal facility deployment, inventory control strategies, and the corresponding cost constitutions are drawn.     

Solving train formation problem using simulated annealing algorithm in a simplex framework

The train formation plan (TFP) determines the train services and their frequencies and assigns the demands. The TFP models are often formulated as a capacitated service network design problem, and the optimal solution is normally difficult to find. In this paper, a hybrid algorithm of the Simplex method and simulated annealing is proposed for the TFP problem. The basic idea of the proposed algorithm is to use a simulated annealing algorithm to explore the solution space, where the revised Simplex method evaluates, selects, and implements the moves. In the proposed algorithm, the neighborhood structure is based on the pivoting rules of the Simplex method that provides an efficient method to reach the neighbors of the current solution. A state‐of‐the‐art method is applied for parameters tuning by using the design of experiments approach. To evaluate the proposed model and the solution method, 25 test problems have been simulated and solved. The results show the efficiency and the effectiveness of the proposed approach. The proposed approach is implemented to develop the TFP in the Iranian railway as a case study. It is possible to save significant time and cost through solving the TFP problem by using the proposed algorithm and developing the efficient TFP plan in the railway networks. Copyright © 2012 John Wiley & Sons, Ltd.     

Bicriterion shortest path problem with a general nonadditive cost

A bicriterion shortest path problem with a general nonadditive cost seeks to optimize a combination of two path costs, one of which is evaluated by a nonlinear function. This paper first identifies a number of emerging transportation applications for which such a shortest path problem might be considered a core subproblem. We propose to first approximate the general nonlinear cost function with a piecewise linear counterpart, and then solve each linear subproblem sequentially. A specialized algorithm is developed to solve the subproblems, which makes use of the efficient path set (or the convex hull) to update upper and lower bounds of the original problem. Conditions under which the solution to a subproblem must belong to the efficient path set are specified. Accordingly, we show that the optimal path must be efficient if the nonlinear cost function is concave. If the optimal path to a subproblem is not efficient, partial path enumeration, implemented using a simple K-shortest path ranking procedure, is conducted to close the gap. The proposed algorithm includes strategies aiming to expedite path enumeration by using upper bounds derived from the efficient path set. Numerical experiments are conducted to demonstrate correctness and effectiveness of the proposed algorithm.