Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.07.010 Byline: Joseph Geunes (a), Zuo-Jun Max Shen (b), Akin Emir (c) Keywords: Revenue management; Pricing; Vehicle routing problem Abstract: Classical vehicle routing problems typically do not consider the impact of delivery price on the demand for delivery services. Existing models seek the minimum sum of tour lengths in order to serve the demands of a given set of customers. This paper proposes approximation models to estimate the impacts of price on delivery services when demand for delivery service is price dependent. Such models can serve as useful tools in the planning phase for delivery service providers and can assist in understanding the economics of delivery services. These models seek to maximize profit from delivery service, where price determines demand for deliveries as well as the total revenue generated by satisfying demand. We consider a variant of the model in which each customer's delivery volume is price sensitive, as well as the case in which customer delivery volumes are fixed, but the total number of customers who select the delivery service provider is price sensitive. A third model variant allows the delivery service provider to select a subset of delivery requests at the offered price in order to maximize profit. Author Affiliation: (a) Department of Industrial and Systems Engineering, University of Florida, United States (b) Department of Industrial Engineering and Operations Research, University of California, 4141 Etcheverry Hall, Berkeley, CA 94720-1777, United States (c) Merck and Co., Inc., West Point, PA, United States Article History: Received 5 January 2006; Accepted 17 July 2006

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.04.015 Byline: Leon Yang Chu (a)(b), Zuo-Jun Max Shen (b) Keywords: Mechanism design; Double auction; Strategy-proof mechanism Abstract: With the growth of electronic markets, designing double auction mechanisms that are applicable to emerging market structures has become an important research topic. In this paper, we investigate two truthful double auction design approaches, the Trade Reduction Approach and the Multi-Stage Design Approach, and compare their resulting mechanisms in various exchange environments. We find that comparing with the Trade Reduction Approach, the Multi-Stage Design Approach offers mechanisms applicable to more complicated exchange environments. Furthermore, for the known trade reduction mechanisms, we prove that the corresponding mechanisms under the multi-stage design approach are superior in terms of both social efficiency and individual payoffs, in each exchange environment of interest. Our computational tests show that the mechanisms under the multi-stage design approach achieve very high efficiency in various scenarios. Author Affiliation: (a) Marshall School of Business, University of South California, Los Angeles, CA 90089, United States (b) Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA 94720, United States Article History: Received 23 May 2005; Accepted 3 April 2006

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.03.032 Byline: Zuo-Jun Max Shen (a), Lian Qi (b) Keywords: Location models; Vehicle routing; Inventory; Integrated supply chain design models Abstract: We consider a supply chain design problem where the decision maker needs to decide the number and locations of the distribution centers (DCs). Customers face random demand, and each DC maintains a certain amount of safety stock in order to achieve a certain service level for the customers it serves. The objective is to minimize the total cost that includes location costs and inventory costs at the DCs, and distribution costs in the supply chain. We show that this problem can be formulated as a nonlinear integer programming model, for which we propose a Lagrangian relaxation based solution algorithm. By exploring the structure of the problem, we find a low-order polynomial algorithm for the nonlinear integer programming problem that must be solved in solving the Lagrangian relaxation sub-problems. We present computational results for several instances of the problem with sizes ranging from 40 to 320 customers. Our results show the benefits of having an integrated supply chain design framework that includes location, inventory, and routing decisions in the same optimization model. Author Affiliation: (a) Department of Industrial Engineering and Operations Research, University of California, 4141 Etcheverry Hall, Berkeley, CA 94720-1777, USA (b) Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, USA Article History: Received 9 March 2005; Accepted 25 March 2006

• We provide a review of existing operations studies of electric vehicles (EVs). • This review focuses on mathematical modeling-based solutions to EV operations management problems. • The literature is grouped into EV charging infrastructure planning, EV charging operations, and public policy and business models. • New research opportunities for operations management of EVs are suggested. Electric vehicles (EVs) are widely considered to be a solution to the problems of increasing carbon emissions and dependence on fossil fuels. However, the adoption of EVs remains sluggish due to range anxiety, long charging times, and inconvenient and insufficient charging infrastructure. Various problems with EV service operations should be addressed to overcome these challenges. This study reviews the state-of-the-art mathematical modeling-based literature on EV operations management. The literature is classified according to recurring themes, such as EV charging infrastructure planning, EV charging operations, and public policy and business models. In each theme, typical optimization models and algorithms proposed in previous studies are surveyed. The review concludes with a discussion of several possible questions for future research on EV service operations management. [ABSTRACT FROM AUTHOR]

A bi-attribute concave shortest path (BC-SP) problem seeks to find an optimal path in a bi-attribute network that minimizes a linear combination of two path costs, one of which is evaluated by a nondecreasing concave function. Due to the nonadditivity of its objective function, Bellman’s principle of optimality does not hold. This paper proposes a parametric search method to solve the BC-SP problem, which only needs to solve a series of shortest path problems, i.e., the parameterized subproblems (PSPs). Several techniques are developed to reduce both the number of PSPs and the computation time for these PSPs. Specifically, we first identify two properties of the BC-SP problem to guide the parametric search using the gradient and concavity of its objective function. Based on the properties, a monotonic descent search (MDS) and an intersection point search (IPS) are proposed. Second, we design a speedup label correcting (LC) algorithm, which uses optimal solutions of previously solved PSPs to reduce the number of labeling operations for subsequent PSPs. The MDS, IPS and speedup LC techniques are embedded into a branch-and-bound based interval search to guarantee optimality. The performance of the proposed method is tested on the mean-standard deviation shortest path problem and the route choice problem with a quadratic disutility function. Experiments on both real transportation networks and grid networks show that the proposed method reduces the computation time of existing algorithms by one to two orders of magnitude. [ABSTRACT FROM AUTHOR]

Traditionally, customers always hail empty-cruising taxis on streets, which may offer low levels of comfort and efficiency especially during rush hours or rainy days. Thanks to the advance of smartphone technology, the e-hailing applications, which enable customers to hail taxis through their smartphones, become popular globally. To provide a systematic account of the impact of e-hailing applications’ wide adoption on the taxi system, we first propose a spatial equilibrium model that not only balances the supply and demand of taxi services but also captures both the taxi drivers’ and customers’ possible adoption of the newly-emerging e-hailing applications in a well-regulated taxi market. We then prove the existence of the proposed equilibrium, and further provide an algorithm to solve it. An extensive equilibrium model with elastic taxi-customer demands is also proposed. Lastly, a numerical example is presented to compare the taxi services with and without the e-hailing application and evaluate two types of e-hailing applications. [ABSTRACT FROM AUTHOR]

When there are significant service disruptions in public transit systems, passengers usually need guidance to find alternative paths. This paper proposes a path recommendation model to mitigate congestion during public transit disruptions. Passengers with different origins, destinations, and departure times are recommended with different paths such that the system travel time is minimized. We model the path recommendation problem as an optimal flow problem with uncertain demand information. To tackle the lack of analytical formulation of travel times due to capacity constraints, we propose a simulation-based first-order approximation to transform the original problem into a linear program. Uncertainties in demand are modeled using robust optimization to protect the path recommendation strategies against inaccurate estimates. A real-world rail disruption scenario in the Chicago Transit Authority (CTA) system is used as a case study. Results show that even without considering uncertainty, the nominal model can reduce the system travel time by 9.1% (compared to the status quo), and outperforms the benchmark capacity-based path recommendation. The average travel time of passengers in the incident line (i.e., passengers receiving recommendations) is reduced more (−20.6% compared to the status quo). After incorporating the demand uncertainty, the robust model can further reduce system travel times. The best robust model can decrease the average travel time of incident-line passengers by 2.91% compared to the nominal model. The improvement of robust models is more prominent when the actual demand pattern is close to the worst-case demand. • A transit path recommendation model for minimizing system travel times under disruptions. • Using robust optimization to consider demand uncertainty. • Propose a simulation-based first-order approximation for the non-tractable objective function. • A case study in the Chicago public transit system with a real-world disruption. • The proposed model can reduce the incident-line passengers' travel time by 20%. [ABSTRACT FROM AUTHOR]

• Large-scale charging station planning for electric buses. • Optimize the planning jointly under the transportation system and power grid. • A spatial-temporal model decides the sites of facilities for multiple stages. • Equivalently transform the model into a mixed-integer second-order cone programming. • Implement a case study of the real-world transportation network in Shenzhen, China. With the applications of electric buses (e-buses), potential solutions to problems related to infrastructures for charging e-buses are emerging. This study particularly focused on large-scale fast charging-station planning for e-buses in the public transportation electrification process, according to the characteristics of e-bus operation and plug-in fast charging mode. We conducted an interdisciplinary study to optimize planning jointly under the transportation system and power grid. In addition to capturing the spatiality of the e-bus charging service network, we further considered temporality in order to conduct long-term planning in view of the continuously growing e-bus charging demand. A spatial-temporal model, which determines the sites and sizes of e-bus charging stations, was proposed and the strategies for multistage infrastructure planning were put forward. The model was equivalently transformed into a mixed-integer second-order cone programming with high computational efficiency. The model and the multistage planning strategies were justified through a series of numerical experiments. A case study of Shenzhen, China was implemented and the robustness of the model to plan changes was studied. [ABSTRACT FROM AUTHOR]

This study introduces a challenging service network design problem with stochastic demands and fixed routes. In this problem, the routes of some service vehicles are fixed during the whole planning horizon, while the remaining vehicles are flexible in that their routes can adapt to different realizations of customer demands each day. The problem is to determine which vehicles should be set as fixed and how their fixed routes should be designed. To solve this problem, we formulate a two-stage stochastic mixed-integer linear program. The fixed routes are designed in the first stage before customer demands are realized, and the routes for flexible vehicles are designed in the second stage after customer demands are observed. A learning-based multiple scenario approach is developed as the solution method. Numerical experiments on real-world operational data from a logistics company show that fixing the routes of some service vehicles may reduce the operational cost by an average of approximately 6.37% compared with that in the case of no fixed routes. • The service network design problem with stochastic demands and fixed routes is introduced. • A two-stage stochastic mixed-integer linear programming model is formulated. • A learning-based multiple scenario approach is developed. • The model and solution algorithm are demonstrated on real-world operational data. [ABSTRACT FROM AUTHOR]

• A data-driven framework is developed to quantify EV performance degradation. • An iterative learning process is proposed for impact decoupling. • EV big data are used for range and energy consumption assessments. • Multiple data sources are coupled by using spatiotemporal data. Electric vehicle (EV) performance in terms of the available driving range per charge and the energy consumption rate continuously degrades during its service life. Quantitative assessments of EV performance degradation play an important role in EV residual value analysis, battery management, and battery recycling. However, EV performance degradation is highly sensitive to both ambient temperature and battery aging states; coupled factors make its quantification challenging. Here, a novel big data-driven decoupling framework is proposed to investigate the partial relationships between EV performance degradation and each individual variable (e.g., temperature and total driving distances). The core innovation involves the decoupling process that can enable real-world and large-scale degradation assessments. The basic functionality of the decoupling is achieved by an iterative learning framework where different machine learning-based models can communicate with each other. It achieves the advantages of unsupervised training and high performance; the mean absolute error can be controlled less than 0.1 in the model validation of EV ranges. Its effectiveness is verified using different real-world EV datasets. By utilizing the framework, the changes in the range and energy consumption of EVs across 10 urban areas in China are assessed. The results show that the range and energy consumption rate of EVs are more greatly influenced by ambient temperature than by battery aging. Less consideration of variable decoupling may yield misleading results in EV performance analysis. Our proposed framework opens avenues for quantifying EV performance degradation via real-world EV data, which is critical to onboard and cloud-based EV research. [ABSTRACT FROM AUTHOR]

The increasing concern over global warming has led to the rapid development of the electric vehicle industry. Electric vehicles (EVs) have the potential to reduce the greenhouse effect and facilitate more efficient use of energy resources. In this paper, we study several EV route planning problems that take into consideration possible battery charging or swapping operations. Given a road network, the objective is to determine the shortest (travel time) route that a vehicle with a given battery capacity can take to travel between a pair of vertices or to visit a set of vertices with several stops, if necessary, at battery switch stations. We present polynomial time algorithms for the EV shortest travel time path problem and the fixed tour EV touring problem , where the fixed tour problem requires visiting a set of vertices in a given order. Based on the result, we also propose constant factor approximation algorithms for the EV touring problem , which is a generalization of the traveling salesman problem. [ABSTRACT FROM AUTHOR]

This study reviews the literature on air cargo operations and compares theoretical studies with the practical problems of airlines, freight forwarders, and terminal service providers. In particular, we review studies in which mathematical models were used to identify the essential characteristics of air cargo operations, such as the intrinsic differences from passenger operations, and to explore the service processes in air cargo operations. The typical models used in previous studies are summarized. We then highlight the insightful findings from an industrial interview and present the gaps between previous research and practical realities. We finally discuss the new research opportunities of air cargo operations according to the gaps. [ABSTRACT FROM AUTHOR]

Abstract: Product substitution can mitigate supply chain disruptions. However, it may not be very effective without multiple sourcing. In this paper, we consider a supply chain with two downward substitutable products. The products can be ordered from an unreliable supplier or a reliable but more expensive supplier. It is found that in an optimal sourcing policy the higher-grade product should be preferred over the lower-grade product. A sufficient condition is given for an optimal policy where only the higher-grade product is dual-sourced. The effect of substitution is contrasted with the non-substitution case. Numerical study shows the impact of demand variability and correlation on the effect of product substitution and the corresponding optimal sourcing policy. [Copyright &y& Elsevier]

• A novel framework for large-scale EV charging energy predictions is introduced. • The MAPE retains at 2.5–3.8% with a testing/training ratio varying from 0.1 to 1000. • MICs and PCCs are combined for feature analyses of charging energy predictions. • Multiple data sources are coupled by linking the timestamps and location data. Large-scale and high-precision predictions of the charging energy required for electric vehicles (EVs) are essential to ensure the safety of EVs and provide reliable inputs for grid-load calculations. However, the complex and dynamic operating conditions of EVs make it challenging to accurately predict the charging energy under real-world conditions, especially for large-scale EV utilization. In this study, a novel data-driven framework for large-scale charging energy predictions is developed by individually controlling the strongly linear and weakly nonlinear contributions. The proposed framework concurrently addresses the overfitting of nonlinear networks using a low proportion of training data as well as the poorly descriptive ability of linear networks under complex environments. For each charging session, the charging energy predictions appropriately account for important factors such as the variations in the state of charge (SOC) of the battery, ambient temperatures, charging rates, and total driving distances. The results suggest that, compared with existing prediction models (such as the random forest, xgboost, and neural network), the proposed framework persists with evidently higher accuracy and stability over a wide range of the ratio between the number of EVs used for testing and training; its mean absolute percentage error (MAPE) is maintained at 2.5–3.8% when the ratio ranges from 0.1 to 1000. The proposed models can be further utilized for cloud-based battery diagnoses and large-scale forecasting of the energy demands of EVs. [ABSTRACT FROM AUTHOR]

In this paper, we define and investigate a novel model-free deep reinforcement learning framework to solve the taxi dispatch problem. The framework can be used to redistribute vehicles when the travel demand and taxi supply is either spatially or temporally imbalanced in a transportation network. While previous works mostly focus on using model-based methods, the goal of this paper is to explore the policy-based deep reinforcement learning algorithm as a model-free method to optimize the rebalancing strategy. In particular, we propose an actor-critic algorithm with feed-forward neural networks as approximations of both policy and value functions, where the policy function provides the optimal dispatch strategy and the value function estimates the expected costs at each time stamp. Our numerical studies show that the algorithm converges to the theoretical upper bound with less than 4% optimality gap, whether the system dynamics are deterministic or stochastic. We also investigate the scenario where we consider user priority and fairness, and the results indicate that our learned policy is capable of producing a superior strategy that balances equity, cancellation, and level of service when user priority is considered. [ABSTRACT FROM AUTHOR]

• We propose a method of producing synthetic connected populations required to advance agent-based exploration of phenomena involving social influence on travel behaviours. • The method reproduces socio-economic characteristics for the synthetic households using a Bayesian network model estimated from household survey data. • The method detects and assigns the population to the observed communities, using an integer programming approach. • The method generates social networks following the Exponential Random Graph Models estimated from the available social network data. • A scalable implementation of the framework is developed (with the source code made available), and illustrated experimentally for a region of the San Francisco Bay Area. Agent-based modeling in transportation problems requires detailed information on each of the agents that represent the population in the region of a study. To extend the agent-based transportation modeling with social influence, a connected synthetic population with both synthetic features and its social networks need to be simulated. However, either the traditional manually-collected household survey data (ACS) or the recent large-scale passively-collected Call Detail Records (CDR) alone lacks features. This work proposes an algorithmic procedure that makes use of both traditional survey data as well as digital records of networking and human behavior to generate connected synthetic populations. The generated populations coupled with recent advances in graph (social networks) algorithms can be used for testing transportation simulation scenarios with different social factors. [ABSTRACT FROM AUTHOR]

Highlights • Joint location and capacity design problem for charging stations. • A novel expanded network structure. • Queuing time approximation formula. • Customized neighborhood search heuristics. Abstract This study is devoted to designing locations and capacities of charging stations for supporting long-distance travel by electric vehicles (EVs). We first establish an expanded network structure to model the set of valid charging strategies for EV drivers, and then a variational inequality (VI) is formulated to capture the equilibrated route-choice and charging behaviors of EVs by incorporating an approximated queuing time function for a capacitated charging facility. Next, we formulate the problem of designing the locations and capacities of charging facilities under a fixed budget constraint and solve the optimization problem with a customized neighborhood search strategy. A lower bound for the system cost is also developed to evaluate the qualities of solutions acquired using our proposed heuristic. Numerical examples with a toy network and a highway network extracted from the Yangtze River Delta are used to show the effectiveness of the proposed methodology, and we observe that our strategy can solve a large-scale problem within an optimality gap of less than 5%. [ABSTRACT FROM AUTHOR]

Motivated by the recent boom of the sharing economy, this paper presents a scheme of sharing demand-side energy resources (DERs) among multiple prosumers. Successful sharing must achieve enhanced utilization efficiency of DERs and, in the mean time, ensure voluntary participation of prosumers and a sharing-enabling aggregator. It is also desirable to incentivize the adoption of DERs. To fulfill these goals, we formulate a mathematical program with equilibrium constraints (MPEC) for DER valuation within a sharing community. The aggregator coordinates DER operations in real-time; then it solve this MPEC problem after each billing period. In doing so, the aggregator evaluates two operating costs for each prosumer: the actual cost under coordination and the counter-factual cost if the prosumer independently traded power with the aggregator. We define the difference in these two costs as the coordination surplus, which the aggregator and the prosumer split. Simulation results demonstrate that this sharing procedure effectively achieves the aforementioned goals. [ABSTRACT FROM AUTHOR]

High variability interchange times often significantly affect the reliability of metro travels. Fine-grained measurements of interchange times during metro transfers can provide valuable insights on the crowdedness of stations, usage of station facilities and efficiency of metro lines. Measuring interchange times in metro systems is challenging since agent-operated systems like automatic fare collection systems only provide coarse-grained trip information and popular localization services like GPS are often inaccessible underground. In this paper, we propose a smartphone-based interchange time measuring method from the passengers’ perspective. It leverages low-power sensors embedded in modern smartphones to record ambient contextual features, and utilizes a two-tier classifier to infer interchange states during a metro trip, and further distinguishes 10 fine-grained cases during interchanges. Experimental results within 6 months across over 14 subway lines in 3 major cities demonstrate that our approach yields an overall interchange state inference F1-measurement of 91.0% and an average time error of less than 2 min at an inference interval of 20 s, and an average accuracy of 89.3% to distinguish the 10 fine-grained interchange cases. We also conducted a series of case studies using measurements collected from crowdsourced users during 3 months, which reveals findings previously unattainable without fine-grained interchange time measurements, such as portions of waiting time during interchange, interchange directions, usage of facilities (stairs/escalators/lifts), and the root causes of long interchange times. [ABSTRACT FROM AUTHOR]

We introduce and study a challenging service network design problem arising within a city logistics company based in Beijing, China. To provide cost-effective same-day delivery services, the company divides the whole urban area into regions. Within each region, a fleet of small-capacity vehicles picks up and delivers packages. A fleet of line-haul vehicles (large-capacity vehicles) executes consistent multiple trips over the regions to transport consolidated packages, during which transshipment is allowed. In this study, we focus on designing the trips of line-haul vehicles, i.e., their region visiting sequences, as the performance of the logistics system depends significantly on the coordination of line-haul vehicles. We model the trip design problem as a service network design problem with consistent multiple trips. We develop a continuous-time MIP model to formulate the problem and optimally solve small-size instances. In addition, we propose an adaptive large neighborhood search heuristic to solve larger instances. Numerical experiments on randomly generated instances as well as real-world operational data demonstrate the effectiveness and efficiency of our solution approach. • The service network design problem with consistent multiple trips is introduced. • A continuous-time mixed integer programming model is formulated. • An adaptive large neighborhood search solution algorithm is developed. • The model and solution algorithm are demonstrated on real-world operational data. [ABSTRACT FROM AUTHOR]

Increasing wildfire activity globally has become an urgent issue with enormous ecological and social impacts. In this work, we focus on analyzing and quantifying the influence of landscape topology, understood as the spatial structure and interaction of multiple land-covers in an area, on fire ignition. We propose a deep learning framework, Deep Fire Topology, to estimate and predict wildfire ignition risk. We focus on understanding the impact of these topological attributes and the rationale behind the results to provide interpretable knowledge for territorial planning considering wildfire ignition uncertainty. We demonstrate the high performance and interpretability of the framework in a case study, accurately detecting risky areas by exploiting spatial patterns. This work reveals the strong potential of landscape topology in wildfire occurrence prediction and its implications to develop robust landscape management plans. We discuss potential extensions and applications of the proposed method, available as an open-source software. • We show the impact of different landscape topologies on wildfire ignitions. • We develop a novel and interpretable deep learning framework. • The model detects and highlights low/high-risk land-cover topological patterns. • We obtain accurate fire occurrence predictions only using land-cover data. • Our framework can be applied in any field exploiting computer vision. [ABSTRACT FROM AUTHOR]