- Bogyrbayeva, A., T. Yoon, H. Ko, S. Lim, H. Yun, C. Kwon. (2023) A Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drone. Transportation
Research Part C: Emerging Technologies, 148, 103981 arXiv
github abstract
Reinforcement learning has recently shown promise in learning quality solutions in many combinatorial optimization problems. In particular, the attention-based encoder-decoder models show high effectiveness on various routing problems, including the Traveling Salesman Problem (TSP). Unfortunately, they perform poorly for the TSP with Drone (TSP-D), requiring routing a heterogeneous fleet of vehicles in coordination---a truck and a drone. In TSP-D, the two vehicles are moving in tandem and may need to wait at a node for the other vehicle to join. State-less attention-based decoder fails to make such coordination between vehicles. We propose a hybrid model that uses an attention encoder and a Long Short-Term Memory (LSTM) network decoder, in which the decoder's hidden state can represent the sequence of actions made. We empirically demonstrate that such a hybrid model improves upon a purely attention-based model for both solution quality and computational efficiency. Our experiments on the min-max Capacitated Vehicle Routing Problem (mmCVRP) also confirm that the hybrid model is more suitable for the coordinated routing of multiple vehicles than the attention-based model. The proposed model demonstrates comparable results as the operations research baseline methods.
- Haider, Z., Y. Hu, H. Charkhgard, D. Himmelgreen, C. Kwon. (2022) Creating Grocery Delivery Hubs for Food Deserts at Local Convenience Stores via Spatial and Temporal Consolidation. Socio-Economic
Planning Sciences, 82(B), 101301. doi
pdf abstract
For many socioeconomically disadvantaged customers living in food deserts, the high costs and minimum order size requirements make attended grocery deliveries financially non-viable, although it has potential to provide healthy foods to the food insecure population. This paper proposes consolidating customer orders and delivering to a neighborhood convenience store instead of home delivery. We employ an optimization framework involving the minimum cost set covering and the capacitated vehicle routing problems. Our experimental studies in three counties in the U.S. suggest that by spatial and temporal consolidation of orders, the deliverer can remove minimum order-size requirements and reduce the delivery costs, depending on various factors, compared to attended home-delivery. We find the number and size of time windows for home delivery to be the most important factor in achieving temporal consolidation benefits. Other significant factors in achieving spatial consolidation include the capacity of delivery vehicles, the number of depots, and the number of customer orders. We also find that the number of partner convenience stores and the walkable distance parameter of the model, have a significant impact on the number of accepted orders, i.e., the service level provided by the deliverer. The findings of this study imply consolidated grocery delivery as a viable solution to improve fresh food access in food deserts. In light of the recent global pandemic, and its exacerbating effects on food insecurity, the innovative solution proposed in this paper is even more relevant and timely.
- Bogyrbayeva A., S. Jang, A. Shah, Y. J. Jang, C. Kwon. (2022) A Reinforcement Learning Approach for Rebalancing Electric Vehicle Sharing Systems. IEEE Transactions on Intelligent
Transportation Systems, 23(7), 8704–8714. doi
arXiv pdf
github abstract
This paper proposes a reinforcement learning approach for nightly offline rebalancing operations in free-floating electric vehicle sharing systems (FFEVSS). Due to sparse demand in a network, FFEVSS require relocation of electrical vehicles (EVs) to charging stations and demander nodes, which is typically done by a group of drivers. A shuttle is used to pick up and drop off drivers throughout the network. The objective of this study is to solve the shuttle routing problem to finish the rebalancing work in the minimal time. We consider a reinforcement learning framework for the problem, in which a central controller determines the routing policies of a fleet of multiple shuttles. We deploy a policy gradient method for training recurrent neural networks and compare the obtained policy results with heuristic solutions. Our numerical studies show that unlike the existing solutions in the literature, the proposed methods allow to solve the general version of the problem with no restrictions on the urban EV network structure and charging requirements of EVs. Moreover, the learned policies offer a wide range of flexibility resulting in a significant reduction in the time needed to rebalance the network.
- A. Bogyrbayeva, C. Kwon. (2021) Pessimistic Evasive Flow Capturing Problems. European Journal of Operational Research, 293(1), 133-148.
doi pdf
abstract
The evasive flow capturing problem (EFCP) is to locate a set of law enforcement facilities to intercept unlawful flows. One application of the EFCP is the location problem of weight-in-motion systems deployed by authorities to detect overloaded vehicles characterized by evasive behavior. Although optimistic bilevel formulations of the EFCP are studied in the literature, we provide two pessimistic formulations by relaxing the assumption on the optimizing behavior of unlawful travelers and capturing the ambiguity of travelers' route choices. While the first pessimistic formulation yields the most robust network design, the second pessimistic formulation can flexibly control the level of pessimism on the behavior of followers between optimistic and overly pessimistic. The resulting formulations yield a robust network design and represent realistic behavior of drivers. The pessimistic formulations introduce another level in the optimization problem, for which we propose a cutting plane algorithm. The proposed solution methods demonstrate their effectiveness on real and randomly generated networks. We also compute the value of pessimistic solutions.
- Bogyrbayeva A., M. Takalloo, H. Charkhgard, C. Kwon. (2021) An Iterative Combinatorial Auction Design for Fractional Ownership of Autonomous Vehicles. International Transactions
in Operational Research, 28(4), 1681–1705. doi
pdf abstract
This study designs a new market for fractional ownership of autonomous vehicles (AVs), in which an AV is co-leased by a group of individuals. We present a practical iterative auction based on the {combinatorial clock auction} to match the interested customers together and determine their payments. In designing such an auction, we consider continuous-time items (time slots) which are defined by bidders and naturally exploit driverless mobility of AVs to form co-leasing groups. To relieve the computational burdens of both bidders and the auctioneer, we devise user agents who generate packages and bid on behalf of bidders. Through numerical experiments using the California 2010--2012 travel survey, we test the performance of the auction design. We also compare various bidding strategies and study the effect of {activity rules} on the bidders' payoffs. We find that the designed activity rules successfully remove the strategic behavior of bidders. We also find that {core-selecting payment rule} brings the largest revenue to the auctioneer in most cases.
- Takalloo, M., A. Bogyrbayeva, H. Charkhgard, C. Kwon (2021). Solving the Winner Determination Problem in Combinatorial Auctions for Fractional Ownership of Autonomous Vehicles. International Transactions
in Operational Research, 28(4), 1658–1680. doi
pdf Fractional Ownership; Combinatorial Auction; Bidder-Defined Items; Clique abstract
The introduction of autonomous vehicles to consumer markets will expedite the trend of car-sharing and enable co-owning or co-leasing a car. In this paper, we consider a combinatorial auction market for fractional ownership of autonomous vehicles, which is unique in two aspects. First, items are neither pre-defined nor discrete; rather, items are continuous time slots defined by bidders. Second, the spatial information of bidders should be incorporated within the winner determination problem so that sharing a vehicle is indeed a viable plan. The consideration of spatial information increases the computational complexity significantly. We formulate the winner determination problem, which plays a critical role in various auction designs and pricing schemes, for both discrete- and continuous-time settings. In terms of social welfare maximization, we show that the continuous-time model is superior to the discrete-time model. We provide a conflict-based reformulation of the continuous-time model, for which we develop an effective solution approach based on a heuristic and maximal-clique based reformulations. Using samples of the 2010--2012 California Household Travel Survey, we verify that the proposed solution methods provide effective computational tools for the combinatorial auction with bidder-defined items.
- Takalloo, M., C. Kwon (2020). On the Price of Satisficing in Network User Equilibria. Transportation Science, 54(6), 1555–1570. doi
arXiv pdf bounded rationality; satisficing; user equilibrium; sensitivity analysis abstract
When drivers are satisficing decision-makers, the resulting traffic pattern attains a satisficing user equilibrium, which may deviate from the (perfectly rational) user equilibrium. In a satisficing user equilibrium traffic pattern, the total system travel time can be worse than in the case of the PRUE. We show how bad the worst-case satisficing user equilibrium traffic pattern can be, compared to the perfectly rational user equilibrium. We call the ratio between the total system travel times of the two traffic patterns the price of satisficing, for which we provide an analytical bound. Using the sensitivity analysis for variational inequalities, we propose a numerical method to quantify the price of satisficing for any given network instance.
- Melendez, K.A., T.K. Das, C. Kwon (2020). A Nash-bargaining Model for Trading of Electricity Between Aggregations of Peers. International Journal of Electrical
Power and Energy Systems, 123, 106185. doi
pdf Aggregation of peers; peer-to-peer energy trading; option contract; Nash bargaining solution abstract
In the last several years, the growth in household solar generation and the lack of success of the feed-in-tariff programs have led to the rise of peer-to-peer (P2P) energy trading schemes among prosumers. However, a change that has started more recently is the growth of smart homes and businesses, of which loads are IoT controlled and are supported by advanced metering infrastructure (AMI). This has created a new opportunity for smart homes and businesses to form aggregations (coalitions) and participate in cooperative load management and energy trading. Unlike energy trading among individual prosumers in most P2P networks, a new trading opportunity that is emerging is between aggregations of peers of smart homes and businesses and electric vehicles (EVs). In this paper, we consider one such trading scenario between two aggregations, of which one has smart homes and businesses with load consuming entities (not prosumers), and the other has EVs only. The aggregation with smart homes and businesses derive cost reduction through optimal load scheduling based on load preferences, market-based pricing of electricity, and opportunity to trade (buy) energy from the aggregation with EVs. Whereas the aggregation of EVs optimally schedules charging to meet EV needs and uses stored energy to trade (sell). A generalized Nash bargaining model is developed for obtaining optimal trading strategies in the form of plain or swing option contracts. A sample numerical problem scenario is used to show that suitable contracts can be derived that allow aggregations of peers to mutually benefit from energy trading. Interactions among contract parameters (such as strike price, option value, and option quantity) and the relative market power of the aggregations are also examined.
- Melendez, K.A., T.K. Das, C. Kwon (2020). Optimal operation of a system of charging hubs and a fleet of shared autonomous electric vehicles. Applied Energy, 279, 115861.
doi pdf Shared autonomous electric vehicles, cyber-physical system, ACOPF, energy arbitrage, robust optimization, stochastic optimization
abstract
Shared autonomous electric vehicles (SAEVs) are expected to serve a significant fraction of the passenger transportation needs in cities and surrounding urban areas. In this paper, we consider optimal operation of a cyber-physical system (CPS) comprising a large fleet of SAEVs and a set of charging hubs located across the transportation network and supported by the power grid. The hubs are considered to have a number of charging stations, a stand-alone battery bank for energy storage, and limited rooftop photo-voltaic (PV) generation capacity. We developed a robust mixed integer linear programming model. It considers a number of practical features of both the power and transportation systems, including day-ahead load commitment for electricity via an alternative current power flow model, real time price spikes of electricity, energy arbitrage, uncertainty in passenger demand, and balking of passengers while waiting for a ride. We demonstrated our methodology by implementing it on a sample CPS with 500 SAEVs and five hubs with fifty charging stations in each. Our methodology yields operational decisions for day ahead commitment of power and real time control of the SAEVs and the hubs. The sample CPS is used to examine impact of hub capacity and fleet size on various system performance measures. We discuss the computational challenges of our methodology and propose a simplified myopic approach that is capable of dealing with much larger fleet sizes and a variety of hub capacities. Reduction in computation time and the optimality gap for the myopic approach are examined.
- Su. L., C. Kwon. (2020) Risk-Averse Network Design with Behavioral Conditional Value-at-Risk for Hazardous Materials Transportation. Transportation Science, 54(1), 184–203. doi
pdf transportation; hazardous materials; network design; conditional value-at-risk; Benders decomposition abstract
We consider a road-ban problem in hazardous materials (hazmat) transportation. We formulate the problem as a network design problem to select a set of closed road segments for hazmat traffic and obtain a bi-level optimization problem. While modeling probabilistic route-choices of hazmat carriers by the random utility model (RUM) in the lower level, we consider a risk-averse measure called conditional value-at-risk (CVaR) in the upper level, instead of the widely used expected risk measure. Using RUM and CVaR, we quantify the risk of having hazmat accidents and large consequences, and design the network policy for road-bans accordingly. While CVaR has been used in hazmat routing problems, this paper is the first attempt to apply CVaR in risk averse hazmat network design problems considering stochastic route-choices of hazmat carriers. The resulting problem is a mixed integer nonlinear programming problem, for which we devise a line search approach combined with Benders decomposition. We demonstrate the efficiency of the proposed computational method with case studies. The average computation time for a network with 105 nodes and 268 arcs is 3 hours. Commercial solvers are inadequate to solve this problem, because the optimality gap is 99.9% after 24 hours just for a linear subproblem. By applying CVaR to the route-choice behavior of hazmat carriers, we protect the road network from undesirable route-choices that may lead to severe consequences. We define the Value of RUM-CVaR Solutions (VRCS) over the deterministic model based on shortest-path problems and the expected risk measure. Our case study shows that VRCS can range from 4.9% to 64.1% depending on the probability threshold used in the CVaR measure.
- Zhang, A., J.E. Kang, C. Kwon (2020). Generalized Stable User Matching for Autonomous Vehicle Co-ownership Programs. Service Science, 12(2–3), 61–79. doi
pdf autonomous vehicles; stable matching; roommate matching; car sharing system; vehicle ownership; fractional ownership abstract
We investigate a new form of car sharing system that can be introduced in the market for autonomous vehicles, called fractional ownership or co-ownership. While dynamic ride sharing provides ad-hoc shared mobility services without any long-term commitment, we consider co-ownership programs with which users can still ``own'' a car with committed usages and ownership. We assume that an autonomous vehicle is shared by a group of users, which is only accessible by the group. We use stable matching to help users find an appropriate group to share an autonomous vehicle and present a generalized stable matching model that allows flexible sizes of groups as well as various alternative objectives. We also present a heuristic algorithm to improve computational time due to the combinatorial property of the problem.
- Zhang, A., J. E. Kang, C. Kwon (2020). Multi-day Scenario Analysis for Battery Electric Vehicle Feasibility Assessment and Charging Infrastructure Planning. Transportation Research Part C: Emerging Technologies,
111, 439–457. doi pdf activity-travel patterns; battery electric vehicle; charging infrastructure planning; level 3 charging
abstract
Multi-day activity-travel patterns help create potential vehicle usage profiles that contain vehicle operations and battery status under different scenarios with varying location-based charging opportunities, based on travel needs and charging availability/behaviors. Utilizing a multi-day data sampling method, analyses of scenarios are designed to provide insights on bounds of potential BEV market under different charging opportunities, including level 2 activity charging and level 3 trip charging. Single-day data results tend to overestimate travelers' BEV feasibility assuming that multi-day sample data provides accurate estimations. Facility utilization can be improved without affecting travelers' charging demand under correct pricing scheme for most cost-sensitive users. Smart grid charging strategy can greatly reduce the total number of operating chargers during the same time in a day, and BEV users' charging behaviors have minor impact on this improvement. Our numerical results indicate that an appropriate number of chargers installed in shopping and leisure locations should be more profitable and have higher charger utilization rate since those chargers help cover BEV users' trips.
- Taslimi, M., R. Batta, C. Kwon (2020). Medical Waste Collection Considering Transportation and Storage Risk. Computers & Operations Research, 120, 104966.
doi pdf medical waste collection; hazardous materials transportation; vehicle routing; decomposition-based heuristic
abstract
We consider a Periodic Load-dependent Capacitated Vehicle Routing Problem (PLCVRP) encountered by healthcare centers and medical waste collection companies for the design of a weekly inventory routing schedule to transport medical wastes to treatment sites. In addition to minimization of transportation risk, occupational risk related to temporary storage of hazardous wastes at the healthcare centers is considered. The transport risk on each arc is dependent on the weight of hazardous medical waste on the vehicle when it traverses that arc. We devise a decomposition based heuristic algorithm to solve this problem. We analyze the characteristics of the PLCVRP\T1\textquoteright s solutions with respect to four different criteria: (i) transport and occupational risk, (ii) transport risk, (iii) occupational risk, and (iv) transportation cost. Solving different versions of PLCVRP reveals that minimizing both transport and occupational risk on the network can aid decision makers to develop a better routing schedule in terms of the imposed risk of hazardous medical waste. Experimental results confirm the efficiency of our heuristic. We present a case study to illustrate solution attributes obtained by our solution methodology. The case study is based on medical waste management in Dolj, Romania.
- Takalloo, M., C. Kwon (2020). Sensitivity of Wardrop Equilibria: Revisited. Optimization Letters, 14, 781–796. doi
arXiv pdf Wardrop equilibria; Selfish routing; Sensitivity analysis
abstract
For single-commodity networks, the increase of the price of anarchy is bounded by a factor of $(1+\varepsilon )^p$ from above, when the travel demand is increased by a factor of $1+\varepsilon $ and the latency functions are polynomials of degree at most $p$. We show that the same upper bound holds for multi-commodity networks and provide a lower bound as well.
- Liu, X., C. Kwon. (2020) Exact Robust Solutions for the Combined Facility Location and Network Design Problem in Hazardous Materials Transportation. IISE Transactions, 52(10), 1156–1172. (Runner-up, Student Paper Competition of
the INFORMS Section on Location Analysis (SOLA), 2019) doi
pdf bi-level optimization; facility location; network design; cutting plane; Benders decomposition; hazardous materials abstract
We consider a leader-follower game in the form of a bi-level optimization problem that simultaneously optimizes facility locations and network design in hazardous materials transportation. In the upper level, the leader intends to reduce the facility setup cost and the hazmat exposure risk, by choosing facility locations and road segments to close for hazmat transportation. When making such decisions, the leader anticipates the response of the followers who wants to minimize the transportation costs. Considering uncertainty in the hazmat exposure and the hazmat transport demand, we consider a robust optimization approach with multiplicative uncertain parameters and polyhedral uncertainty sets. The resulting problem has a min-max problem in the upper level and a shortest-path problem in the lower level. We devise an exact algorithm that combines a cutting plane algorithm with Benders decomposition.
- Eaton, M., S. Yurek, Z. Haider, M. Julien, F. Johnson, B. Udell, H. Charkhgard, C. Kwon. (2019) Spatial Conservation Planning under Uncertainty: Adapting to Climate Change Risks using Modern Portfolio Theory.
Ecological Applications, 29(7):e01962. doi Reserve design, spatial conservation planning, modern portfolio theory, multi-criteria decision analysis, risk management, sea-level rise, urbanization, climate uncertainty abstract
Climate change and urban growth impact habitats, species, and ecosystem services. To buffer against global change, an established adaptation strategy is designing protected areas to increase representation and complementarity of biodiversity features. Uncertainty regarding the scale and magnitude of landscape change complicates reserve planning and exposes decision makers to risk of failing to meet conservation goals. Conservation planning tends to treat risk as an absolute measure, ignoring the context of the management problem and risk preferences of stakeholders. Application to conservation of risk management theory emphasizes diversification of portfolio of assets, with the goal of reducing the impact of system volatility on investment return. We use principles of Modern Portfolio Theory (MPT), which quantifies risk as the variance and correlation among assets, to formalize diversification as an explicit strategy for managing risk in climate-driven reserve design. We extend MPT to specify a framework that evaluates multiple conservation objectives, allows decision makers to balance management benefits and risk when preferences are contested or unknown, and includes additional decision options such as parcel divestment when evaluating candidate reserve designs. We apply an efficient search algorithm that optimizes portfolio design for large conservation problems and a game theoretic approach to evaluate portfolio tradeoffs that satisfy decision makers with divergent benefit and risk tolerances, or when a single decision maker cannot resolve their own preferences. Evaluating several risk profiles for a case study in South Carolina, our results suggest that a reserve design may be somewhat robust to differences in risk attitude but that budgets will likely be important determinants of conservation planning strategies, particularly when divestment is considered a viable alternative. We identify a possible fiscal threshold where adequate resources allow protecting a sufficiently diverse portfolio of habitats such that the risk of failing to achieve conservation objectives is considerably lower. For a range of sea-level rise projections, conversion of habitat to open water (14--180%) and wetland loss (1--7%) are unable to be compensated under the current protected network. In contrast, optimal reserve design outcomes are predicted to ameliorate expected losses relative to current and future habitat protected under the existing conservation estate.
- Subramanian, V. T. K. Das, C. Kwon, A. Gosavi (2019). A Data-Driven Methodology for Dynamic Pricing and Demand Response in Electric Power Networks. Electric Power Systems Research, 174, 105869.
doi pdf dynamic pricing; aggregated demand response; electric power network; Bayesian demand prediction
abstract
The practice of disclosing price of electricity before consumption (dynamic pricing) is essential to promote aggregator-based demand response in smart and connected communities. However, both practitioners and researchers have expressed fear that wild fluctuations in demand response resulting from dynamic pricing may adversely affect the stability of both the network and the market. This paper presents a comprehensive methodology guided by a data-driven learning model to develop stable and coordinated strategies for both dynamic pricing as well as demand response. The methodology is designed to learn offline without interfering with network operations. Application of the methodology is demonstrated using simulation results from a sample 5-bus PJM network. Results show that it is possible to arrive at stable dynamic pricing and demand response strategies that can reduce cost to the consumers as well as improve network load balance.
- Melendez, K. A. , V. Subramanian, T. K. Das, C. Kwon (2019). Empowering end-use consumers of electricity to aggregate for demand-side participation. Applied Energy, 248, 372–382.
doi Demand-side participation; Aggregation of end-use consumers; Fairness; Peer-to-peer trading; Energy sharing using EVs; Optimization of power systems abstract
End-use consumers (peers) are being empowered to aggregate for direct demand-side participation through load scheduling and energy sharing. This is the result of the growth of Internet of Things (IoT) enabled loads, availability of advanced metering infrastructure, and the move towards real-time (RT) pricing of electricity. Peer-to-peer (P2P) cooperation has received significant interest in recent years, though the focus of this growing body of research is on modeling prosumer behavior in microgrids. Hence, there is a need for new methodologies to examine empowerment of all end-use consumers (not limited to prosumers) to form aggregations and develop fair rules of cooperation to reduce cost. This paper offers an optimization based methodology to address the above need for power systems. It minimizes the total cost and considers fairness using a Nash bargaining approach. Since cost and fairness are often in conflict, trade-off strategies are also presented. The model to asses fairness is nonlinear. Hence, it is transformed into a second order cone program (SOCP) and solved using GUROBI software version 7.5.2. The methodology is implemented on a sample 5-bus network, built using price and demand data from one of the load zones of Pennsylvania, New Jersey, and Maryland (PJM) power network in the United States. It is shown that two aggregations of peers participating in the sample network can reduce their total cost by 14.17% and 22.7%, while maintaining fairness. Concluding remarks highlight some of the limitations of the methodology.
- Sun, L., M. Karwan, C. Kwon (2019). Path-Based Approaches to Robust Network Design Problems Considering Boundedly Rational Network Users. Transportation Research Record, 2673(3), 637–645.
doi pdf networks and graphs; satisficing; network design; hazardous materials; bi-level optimization
abstract
Network users may choose non-shortest paths, when (1) they satisfice with sub-optimal routes, or (2) they have perception errors of the decision environment. The notion of generalized bounded rationality has been recently proposed to create a unified framework for these two sources of behavioral uncertainty in route choices. When the notion of generalized bounded rationality is used in robust network design problems, we obtain a bi-level optimization problem with the min-max objective function at the upper level, with three layers of optimization in total. In this paper, we derive equivalent single-level path-based formulations that are readily solvable by available optimization libraries. We show how to incorporate them into robust multi-commodity network design problems in hazardous materials transportation.
- Su, L., L. Sun, M. Karwan, C. Kwon (2019). Spectral Risk Measure Minimization in Hazardous Materials Transportation. IISE Transactions, 59(6), 638–652. (Featured in IISE
Magazine) doi pdf
hazardous materials transportation; risk management; spectral risk; coherent risk measures abstract
Due to catastrophic consequences of potential accidents in hazardous materials (hazmat) transportation, a risk-averse approach for routing is necessary. In this paper, we consider spectral risk measures, for risk-averse hazmat routing, which overcome challenges posed in the existing approaches such as conditional value-at-risk. In spectral risk measures, one can define the spectrum function precisely to reflect the decision maker's risk preference. We show that spectral risk measures can provide a unified routing framework for popular existing hazmat routing methods based on expected risk, maximum risk, and conditional value-at-risk. We first consider a special class of spectral risk measures, for which the spectrum function is represented as a step function. We develop a mixed integer linear programming model in hazmat routing to minimize these special spectral risk measures and propose an efficient search algorithm to solve the problem. For general classes of spectral risk measures, we suggest approximation methods and path-based approaches. We propose an optimization procedure to approximate general spectrum functions using a step function. We illustrate the usage of spectral risk measures and the proposed computational approaches using data from real road networks.
- Saghand, P.G., H. Charkhgard, C. Kwon (2019). A Branch-and-Bound Algorithm for a Class of Mixed Integer Linear Maximum Multiplicative Programs: A Multi-objective Optimization Approach. Computers & Operations Research, 101, 263–274.
doi pdf Multiplicative programming; Multi-objective optimization; Optimization over the efficient set; Linear programming; Branch-and-bound algorithm
abstract
We present a linear programming based branch-and-bound algorithm for a class of mixed integer optimization problems with a bi-linear objective function and linear constraints. This class of optimization problems can be viewed as a special case of the problem of optimization over the set of efficient solutions in multi-objective optimization. It is known that when there exists no integer decision variable, such a problem can be solved in polynomial time. In fact, in such a case, the problem can be transformed into a Second-Order Cone Program (SOCP) and so it can be solved efficiently by a commercial solver such as CPLEX SOCP solver. However, in a recent study, it is shown that such a problem can be solved even faster in practice by using a bi-objective linear programming based algorithm. So, in this study, we embed that algorithm in an effective branch-and-bound framework to solve mixed integer instances. We also develop several enhancement techniques including preprocessing and cuts. An extensive computational study demonstrate that the proposed branch-and-bound algorithm outperforms a commercial mixed integer SOCP solver. Moreover, the effect of different branching and node selecting strategies is explored.
- Haider, Z., A. Nikolaev, J. E. Kang, C. Kwon (2018). Inventory Rebalancing through Pricing in Public Bike Sharing Systems. European Journal of Operational Research, 270(1),
103–117. doi pdf transportation; bike-sharing; shared-mobility; rebalancing; pricing; heuristics
abstract
This paper presents a new conceptual approach to improve the operational performance of public bike sharing systems using pricing schemes. Its methodological developments are accompanied by experimental analyses with bike demand data from Capital Bikeshare program of Washington, DC. An optimized price vector determines the incentive levels that can persuade system customers to take bicycles from, or park them at, neighboring stations so as to strategically minimize the number of imbalanced stations. This strategy intentionally makes some imbalanced stations even more imbalanced, creating hub stations. This reduces the need for trucks and dedicated staff to carry out inventory repositioning. For smaller networks, a bi-level optimization model is introduced to minimize the number of imbalanced stations optimally. The results are compared with a heuristic approach that adjusts route prices by segregating the stations into different categories based on their current inventory profile, projected future demand, and maximum and minimum inventory values calculated to fulfill certain desired service level requirements. We use a routing model for repositioning trucks to show that the proposed optimization model and the latter heuristic approach, called the iterative price adjustment scheme (IPAS), reduce the overall operating cost while partially or fully obviating the need for a manual repositioning operation.
- Zhang, A., J. E. Kang, K. Axhausen, C. Kwon (2018). Multi-day Activity-Travel Pattern Sampling Based on Single-Day Data. Transportation Research Part
C: Emerging Technologies, 89, 96–112. doi
pdf Activity-Travel Patterns; Day-to-day variability; Interpersonal variability; Sampling Multiday Activity-Travel Patterns abstract
Although it is important to consider multi-day activities in transportation planning, multi-day activity-travel data are expensive to acquire and therefore rarely available. In this study, we propose to generate multi-day activity-travel data through sampling from readily available single-day household travel survey data. A key observation we make is that the distribution of interpersonal variability in single-day travel activity datasets is similar to the distribution of intrapersonal variability in multi-day. Thus, interpersonal variability observed in cross-sectional single-day data of a group of people can be used to generate the day-to-day intrapersonal variability. The proposed sampling method is based on activity-travel pattern type clustering, travel distance and variability distribution to extract such information from single-day data. Validation and stability tests of the proposed sampling methods are presented.
- Haider, Z., H. Charkhgard, C. Kwon (2018). A Robust Optimization Approach for Solving Problems in Conservation Planning. Ecological Modelling, 368, 288–297.
doi pdf conservation planning; robust optimization; invasion control; reserve selection; bi-objective mixed integer linear programming
abstract
In conservation planning, the data related to size, growth and diffusion of populations is sparse, hard to collect and unreliable at best. If and when the data is readily available, it is not of sufficient quantity to construct a probability distribution. In such a scenario, applying deterministic or stochastic approaches to the problems in conservation planning either ignores the uncertainty completely or assumes a distribution that does not accurately describe the nature of uncertainty. To overcome these drawbacks, we propose a robust optimization approach to problems in conservation planning that considers the uncertainty in data without making any assumption about its probability distribution. We explore two of the basic formulations in conservation planning related to reserve selection and invasive species control to show the value of the proposed robust optimization. Several novel techniques are developed to compare the results produced by the proposed robust optimization approach and the existing deterministic approach. For the case when the robust optimization approach fails to find a feasible solution, a novel bi-objective optimization technique is developed to handle infeasibility by modifying the level of uncertainty. Some numerical experiments are conducted to demonstrate the efficacy of our proposed approach in finding more applicable conservation planning strategies.
- Chung, B.D., S. Park, C. Kwon (2018). Equitable Distribution of Recharging Stations for Electric Vehicles. Socio-Economic Planning Science, 63, 1–11.
doi pdf electric vehicles; flow refueling location problem; demand equity; flow equity
abstract
Given the limited driving range of battery electric vehicles and lack of sufficient charging infrastructure, locating charging stations is an important decision problem to enable long-distance travels by battery electric vehicles. This paper considers an important political factor in such location problems: the equitable access to charging stations among geographical regions. We propose three types of equity constraints to the flow refueling location model: two constraints based on travel demand and the other based on flow. For solving the problem with flow equity constraints, we propose a multi-phase heuristic method. We test the proposed models and computational method in a real expressway network in Korea.
- Sun, L., M. Karwan, C. Kwon (2018). Generalized Bounded Rationality and Robust Multicommodity Network Design. Operations Research, 66(1), 42–57. (Outstanding Paper Award in
Urban Transportation Planning and Modeling, the INFORMS Transportation Science & Logistics (TSL) Society,
2019) doi pdf bounded rationality; satisficing; perception; network design; robust optimization; inverse optimization
abstract
Often network users are not perfectly rational, especially when they are satisficing---rather than optimizing---decision makers and each individual's perception of the decision environment reflects personal preferences or perception errors due to lack of information. While the assumption of satisficing drivers has been used in modeling route choice behavior, this research uses a link-based perception error model to describe driver's uncertain behavior, without assuming stochasticity. In congestion-free networks, we show that the perception error model is more general than the existing bounded rationality models with satisficing drivers with special cases when the two approaches yield the same results; that is, satisficing under accurate perception is equivalent to optimizing under inaccurate perception. This motivates us to define generalized bounded rationality in route choice behavior modeling. The proposed modeling framework is general enough to capture link-specific cost-perception of drivers. We use a Monte Carlo method to estimate modeling parameter values to guarantee a certain coverage probability in comparison with the random utility model. We demonstrate how the notion of generalized bounded rationality can be used in robust multicommodity network design problems and devise a cutting plane algorithm. We illustrate our approaches in the context of hazardous materials transportation.
- Esfandeh, T., R. Batta, and C. Kwon (2018). Time-Dependent Hazardous-materials Network Design Problem. Transportation Science, 52(2), 454–473.
doi pdf
github hazardous materials transportation; network design; column generation; label setting abstract
We extend the hazardous-materials (hazmat) network design problem to account for the time-dependent road closure as a policy tool in order to reduce hazmat transport risk by altering carriers' departure times and route choices. We formulate the time-dependent network design problem using an alternative-based model with each alternative representing a combined path and departure-time choice. We also present an extended model that can not only account for consecutive time-based road closure policies, but also allow stopping at the intermediate nodes of the network in the routing/scheduling decisions of the carriers. Heuristic algorithms based on column-generation and label-setting are presented. To illustrate the advantages that can be gained through the use of our methodology, we present results from numerical experiments based on a transportation network from Buffalo, NY. To investigate the impact of the extensions, we consider three versions of the problem by gradually refining the model. We show that under consideration of extensions, the design policies are more applicable and effective.
- Toumazis, I., M. Kurt, A. Toumazi, L. Karakosta, C. Kwon (2017). Comparative Effectiveness of Up-to-Three Lines of Chemotherapy Treatment Plans for Metastatic Colorectal Cancer. Medical Decision Making
doi pdf
abstract
Modern chemotherapy agents transformed standard care for metastatic colorectal cancer (mCRC) but raised concerns about the financial burden of the disease. We studied comparative effectiveness of treatment plans that involve up to three lines of therapies and impact of treatment sequencing on health and cost outcomes. We employed a Markov model to represent the dynamically changing health status of mCRC patients and used Monte-Carlo simulation to evaluate various treatment plans consistent with existing guidelines. We calibrated our model by a meta-analysis of published data from an extensive list of clinical trials and measured the effectiveness of each plan in terms of cost per quality-adjusted life-year (QALY). We examined the sensitivity of our model and results with respect to key parameters in two scenarios serving as base- and worst-cases for patients\T1\textquoteright overall and progression free survivals. The derived efficient frontiers included 7 and 5 treatment plans in base- and worst-cases, respectively. The incremental cost-effectiveness ratio (ICER) ranged between \protect \T1\textdollar 26,260 and \protect \T1\textdollar 152,530 when the treatment plans on the efficient frontiers were compared against the least costly efficient plan in base-case, and between \protect \T1\textdollar 21,256 to \protect \T1\textdollar 60,040 in worst-case. All efficient plans were expected to lead to fewer than 2.5 AEs and on average successive AEs were spaced more than 9 weeks apart from each other in base-case. Based on ICER, all efficient treatment plans exhibit at least 87% chance of being efficient. Sensitivity analyses show that the ICERs were most dependent on drug acquisition cost, distributions of progression free and overall survivals, and health utilities. We conclude that improvements in health outcomes may come at high incremental costs and are highly dependent in the order treatments are administered.
- Zhang, A., J.E. Kang, C. Kwon (2017). Incorporating Demand Dynamics in Multi-Period Capacitated Fast-charging Location Planning for Electric Vehicles. Transportation Research Part B: Methodological, 103, 5–29.
doi pdf
github electric vehicles; facility location; flow refueling location problem; multi-period planning; vehicle market demand dynamics; alternative fuel vehicles abstract
We develop a multi-period capacitated flow refueling location problem for electric vehicles (EVs) as EV market responds to the charging infrastructure. The optimization model will help us determine the optimal location of chargers as well as the number of charging modules at each station over multiple time periods. We define a number of demand dynamics, including flow demand growth varying with charging opportunities on path as well as demand growing naturally with less affect from charging infrastructure, with two objective functions (one maximizing flow coverage and the other maximizing electric vehicle demand). A case study based on a road network around Washington, D.C., New York City, and Boston is presented to provide numerical experiments related to demand dynamics, showing the potential problems in multi-period planning.
- Ahmed, M.T., J. Zhuang and C. Kwon (2017). Understanding Conflicting Interests of a Government and a Tobacco Manufacturer: A Game-Theoretic Approach. Group Decision and Negotiation, 26(6), 1209–1230.
doi pdf Farming; Subsidy; Food security; Rice; Tobacco; Nash Equilibrium
abstract
Rice is the staple food of nearly half of the population of the world, most of whom live in developing countries. Ensuring a domestic supply of rice from outside sources is difficult for developing countries as less than 5% of the total world\T1\textquoteright s production is available for international trade. Hence, in order to ensure domestic food security, e.g., food availability and access, governments provide subsidies in agriculture. In many occasions, public money used for the subsidy goes toward promoting undesirable crops like tobacco. Although the strategic interaction between governments and manufacturers is critical, it has not been studied in the literature. This study fills this gap by considering a game between a government (of a developing country) and a tobacco manufacturer in which the government decides on a mix of subsidies and the tobacco manufacturer decides on declaring a purchasing price of tobacco. We provide a numerical study to show that controlling the output harvest price is more effective in reaching the desired end result for both the government and the tobacco manufacturer. A subsidy in fertilizer results in the measurable increase in the government spending but does not have significant effect in reaching the production target. The fertilizer subsidy should be provided only when the output price is too high to be affordable for the population.
- Taslimi, M., R. Batta, C. Kwon (2017). A Comprehensive Modeling Framework for Hazmat Network Design, Hazmat Response Team Location, and Equity of Risk. Computers & Operations Research, 79, 119–130.
doi pdf Hazmat emergency response team; Bi-level network design; Greedy heuristic algorithm; Equity of risk; Robust solution
abstract
This paper considers a bi-level hazmat transportation network design problem in which hazmat shipments have to be transported over a road network between specified origin-destination points. The bi-level framework involves a regulatory authority and hazmat carriers. The control variables for the regulatory authority are locations of hazmat response teams and which additional links to include for hazmat travel. The regulatory authority (upper level) aims to minimize the maximum transport risk incurred by a transportation zone, which is related to risk equity. Our measure of risk incorporates the average response time to the hazmat incidents. Hazmat carriers (lower level) seek to minimize their travel cost. Using optimality conditions, we reformulate the non-linear bi-level model into a single-level mixed integer linear program, which is computationally solvable for medium size problems using a commercial solver. For large size problems, we propose a greedy heuristic approach, which we empirically demonstrate to find good solutions with reasonable computational effort. We also seek a robust solution to capture stochastic characteristics of the model. Experimental results are based on popular test networks from the Sioux Falls and Albany areas.
- Li, X., R. Batta, C. Kwon (2017). Effective and Equitable Supply of Gasoline to Impacted Areas in the Aftermath of a Natural Disaster. Socio-Economic Planning Sciences, 57, 25–34.
doi pdf humanitarian logistics, disaster operations management, location, allocation
abstract
The focus of this research is on supplying gasoline after a natural disaster. There are two aspects for this work: determination of which gas stations should be provided with generators (among those that do not have electric power) and determination of a delivery scheme that accounts for increased demand due to lack of public transportation and considerations such as equity. We develop an MIP for this situation. Two case studies based on Hurricane Sandy in New Jersey are developed and solved in CPLEX.
- Chung, S. H. and C. Kwon (2016). Integrated Supply Chain Management for Perishable Products: Dynamics and Oligopolistic Competition Perspectives with Application to Pharmaceuticals. International Journal of Production Economics, 179, 117–129.
doi pdf pharmaceutical supply chain, perishable inventory dynamics, oligopolistic competition, variational inequality, interior point methods
abstract
We propose an integrated supply chain management framework that allows us to explicitly consider the impact of product perishability on a broad scale that includes manufacturers, distribution centers, wholesalers, and demand markets. The framework proposed herein also makes it possible to consider the oligopolistic competition across wholesalers that drives price and demand fluctuations. Furthermore, the supply chain decision rules are derived from necessary conditions in the framework. The inclusion of such salient features allows the framework to generate outcomes that suggest realistic managerial insights. We provide a numerical example in which two multi-national pharmaceutical firms producing a homogeneous medicinal drug and four oligopolistic wholesalers are considered.
- Sun, L., M. Karwan, and C. Kwon (2016). Robust Hazmat Network Design Problems Considering Risk Uncertainty. Transportation Science, 50(4), 1188–1203.
doi pdf hazardous materials transportation; network design; robust optimization
abstract
We study robust network design problems for hazardous materials transportation considering risk uncertainty. Risk uncertainty is considered in two ways: (1) uncertainty on each link across all shipments, and (2) uncertainty on each link for each shipment. We extend an existing heuristic framework to solve these two robust network design problems and propose a Lagrangian relaxation heuristic to solve subproblems within the framework. We present our computational experiences and illustrate general insights based on real networks.
- Toumazis, I. and C. Kwon (2016). Worst-case Conditional Value-at-Risk Minimization for Hazardous Materials Transportation. Transportation Science, 50(4), 1174–1187.
doi pdf
github hazardous materials transportation; conditional value-at-risk; robust optimization abstract
Despite significant advances in risk management, routing hazardous materials (hazmat) has relied on relatively simpler methods. In this paper, we formally introduce an advanced risk measure, called conditional value-at-risk (CVaR), applied to truck routing problems for hazmat transportation. We find that CVaR offers a flexible, risk-averse, and computationally tractable routing method that is adequate to mitigate hazmat accidents. We further extend CVaR to consider the worst-case CVaR (WCVaR) under data uncertainty. The two important data types in hazmat transportation are accident probabilities and accident consequences, both of which are subject to many ambiguous factors. In addition, historical data are usually insufficient to construct probability distribution of accident probabilities and consequences. This motivates a new robust optimization approach to consider and compute WCVaR. Important axioms are studied for both CVaR and WCVaR risk measures to be coherent and appropriate in the context of hazmat transportation, and computational methods are proposed. We demonstrate the proposed notions of CVaR and WCVaR through a case study in a realistic road network.
- Kumar, A. A., J. E. Kang, C. Kwon, and A. Nikolaev (2016). Inferring Origin-Destination Pairs and Utility-Based Travel Preferences for Shared Mobility Systems Users in a Multi-Modal Environment. Transportation Research
Part B: Methodological, 91, 270–291. doi
pdf Origin-Destination estimation, Traveler preferences, Expectation Maximization, Probabilistic inference, Multimodal route choice, Bike Sharing Systems, Shared Mobility Systems abstract
This paper presents a methodological framework to identify population-wide traveler type distribution and simultaneously infer individual travelers' Origin-Destination (OD) pairs, based on the individual records of a shared mobility (bike) system use in a multimodal travel environment. Given the information about the travelers' outbound and inbound bike stations under varied price settings, the developed Selective Set Expectation Maximization (SSEM) algorithm infers an underlying distribution of travelers over the given traveler ``types. or ``classes. treating each traveler's OD pair as a latent variable; the inferred most likely traveler type for each traveler then informs their most likely OD pair. The experimental results based on simulated data demonstrate high SSEM learning accuracy both on the aggregate and dissagregate levels.
- Sun, L., M. H. Karwan, C. Kwon (2016). Implications of Cost Equity Consideration in Hazmat Network Design. Transportation Research Record, 2567(1),
67–77. doi pdf
abstract
The hazmat network design problem (HNDP) aims to reduce the risk of transporting hazmat in the network by enforcing regulation policies. The goal of reducing risk can increase cost for different hazmat carriers. Since HNDP involves multiple parties, it is essential to take the cost increase of all carriers into consideration for the implementation of the regulation policy. While we can consider cost by placing upper bounds on the total increase, the actual cost increase for various OD pairs can differ, which results in unfairness among carriers. Thus we propose to consider the cost equity issue as well in HNDP. Additionally, due to the existence of multiple solutions in current HNDP models and the possibility of unnecessarily closing road segments, we introduce a new objective considering the length of all the closed links. Our computational experience is based on a real network and we show results under different cost consideration cases.
- Esfandeh, T., C. Kwon, R. Batta (2016). Regulating Hazardous Materials Transportation by Dual Toll Pricing. Transportation Research Part B: Methodological, 83, 20–35.
doi pdf hazardous material transportation; toll setting; non-convex optimization; bi-level programming
abstract
We investigate dual-toll setting as a policy tool to mitigate the risk of hazardous material (hazmat) shipment in road networks. We formulate the dual-toll problem as a bi-level program wherein the upper level aims at minimizing the risk, and the lower level explores the user equilibrium decision of the regular vehicles and hazmat carriers given the toll. When the upper level objective is to minimize the risk and all links are tollable, we decompose the formulation into first-stage and second-stage, and suggest a computational method to solve each stage. Our two-stage solution methodology guarantees nonnegative valid dual tolls regardless of the solution accuracy of the first-stage problem. We also consider a general dual-toll setting problem where the regulator rather wishes to minimize a combination of risk and the paid tolls and/or some links are untollable. To solve this truly bilevel problem, we provide heuristic algorithms that decompose the problem into subproblems each being solved by a line search. Case studies based on the Sioux Falls network illustrate the insights on the dual-toll policies.
- Sun, L., M. Karwan, and C. Kwon (2016). Incorporating Driver Behaviors in Network Design Problems: Challenges and Opportunities. Transport Reviews, 36(4), 454–478.
doi pdf
network design; behavior route choice; random utility; random regret; bounded rationality; cumulative prospect theory; fuzzy logic; dynamic learning; SILK theory abstract
The goal of network design problem (NDP) is to make optimal decisions to achieve a certain objective such as minimizing total travel time or maximizing tolls collected in the network. A critical component to NDP is how travelers make their route choices. Researchers in transportation have adopted human decision theories to describe more accurate route choice behaviors. In this paper, we review the NDP with various route choice models: the random utility model (RUM), Random Regret-Minimization (RRM) model, bounded rationality (BR), cumulative prospect theory (CPT), the fuzzy logic model (FLM) and dynamic learning models (DLM). Moreover, we identify challenges in applying behavioral route choice models to NDP and opportunities for future research.
- Hwang, H., J. Park, S. H. Chang, N. Attard, S. Wells, C. Kwon, K. Friedman (2015). The Ties that Bind: Economic and Freight Transportation Implications of U.S.-Canada Border Bridges Using a Bi-national Transportation Network-Combined Economic Model. Research in
Transportation Business & Management, 16, 32–49. doi
pdf Cross-border freight; trade network analysis; border wait time; Bi-national TransNIEMO abstract
This study combines US-Canada bi-national highway network data with a freight flow dataset using ports of entry (POE) via highway border crossings. Through several sub-procedures, the US and Canada highway systems are integrated into a single network dataset. In addition, border wait time dataset was monitored and analyzed to set the border delay baseline. This dataset enables us to explore the freight traffic pattern between the US and Canada. Weighted Eigenvector Score is computed using a Social Network Analysis tool. The results demonstrate that major regional bodies are the primary users of major POE between the US and Canada. This study not only offers an improved understanding of the economic implications of US-Canada border crossings, but also contributes to developing a simulation tool, a bi-national Transportation-combined National Interstate Economic Model. Such a tool is expected to extend and apply to other contexts, such as transportation and national and bi-national security, among other applications. Additionally, this study suggests several important considerations for US and Canadian officials charged with devising policy to protect against security threats while facilitating legitimate flows of goods, services and people across the border.
- Hariharan, V.G., D. Talukdar, and C. Kwon (2015). Optimal Targeting of Advertisement for New Products with Multiple Consumer Segments. International Journal of
Research in Marketing, 32(3), 263–271. doi
pdf ssrn new product diffusion; advertisement; targeting; social contagion; dynamic optimization
abstract
Armed with improved targeting technology, firms are increasingly interested to optimize their advertising dollars through consumer segment-specific targeting, particularly while introducing new products. That task becomes especially important in markets with distinct consumer segments \T1\textendash the early market and the main market \T1\textendash that affect each other\T1\textquoteright s adoption behavior. In this study, in contrast to prior normative studies that assume a single-segment market structure, we derive dynamic optimal advertising and segment-specific targeting strategies for firms facing a two-segment market structure. We allow for mutual demand interactions between the two segments, and for the diffusion parameters, advertising sensitivity, and cost of targeting to differ across the segments. We model the effect of advertising as a logarithmic function that accounts for diminishing marginal returns. Among our key findings: From profit optimization perspective, our two-segment model outperforms the single-segment model under multiple diffusion dynamics contexts \T1\textendash especially for the \T1\textquoteleft bimodal chasm\T1\textquoteright and the \T1\textquoteleft early dip followed by bell-shaped\T1\textquoteright type diffusion patterns \T1\textendash even when the cost of targeting the early market is relatively high. Our numerical analyses indicate that the optimal share of advertisement targeted to the early market segment at launch needs to be much higher than the share of the early market segment in the population. Advertising sensitivity, relative cost of targeting the early market, and the proportion of early market consumers in the population have the greatest effects on the optimal time to transition the targeted advertising spending from the early to the main market segment.
- Chung, S. H. and C. Kwon (2015). Multi-Period Planning for Electric-Car Charging Station Locations: a Case of Korean Expressways. European Journal of Operational Research. 242(2), 677–687.
doi pdf
github flow-refueling location; electric vehicles; multi-period planning; Korean Expressways abstract
One of the most critical barriers to widespread adoption of electric cars is the lack of charging station infrastructure. Although it is expected that a sufficient number of charging stations will be constructed eventually, due to various practical reasons they may have to be introduced gradually over time. In this paper, we formulate a multi-period optimization model based on a flow-refueling location model for strategic charging station location planning. We also propose two myopic methods and develop a case study based on the real traffic flow data of the Korean Expressway network in 2011. We discuss the performance of the three proposed methods.
- Lee, T. and C. Kwon (2014). A Short Note on the Robust Combinatorial Optimization Problems with Cardinality Constrained Uncertainty. 4OR, 12(4), 373–378. doi
pdf github robust combinatorial optimization; discrete optimization
abstract
Robust combinatorial optimization problems with cardinality constrained uncertainty may be solved by a finite number of nominal problems. In this paper, we show that the number of nominal problems to be solved can be reduced significantly.
- Park, J., C. Kwon, and M. Son (2014). Economic Implications of the Canada-U.S. Border Bridges: Applying a Binational Economic Model for Canada and the U.S.. Research in Transportation Business and Management,
11, 123–133. doi pdf Border bridges; congestion; freight transportation; economic costs
abstract
This study provides an approach to measure the economic costs stemming from delays on the bridges connecting the U.S. and Canada. We selected the busiest bridges in the U.S. and Canada that connects the Buffalo-Niagara Metropolitan region and the Ontario province. Separated by the Great Lakes and waterways, Ontario has a significant portion of its trade activities with the U.S. by way of freight transportation crossing border bridges connecting the two countries. Using binational economic models, we found that the economic implications of the Canada-U.S. border bridges are in the range of $120,000 to $400,000 per day in total. Furthermore, the binational economic models we developed have provided which industries are most impacted from the freight delays on the bridges based on diverse scenarios. Our modeling approach and scenario development process provide diverse simulation tests with the changes of freight transportation costs and patterns for key sectors.
- Kang, Y., R. Batta and C. Kwon (2014). Value-at-Risk Model for Hazardous Material Transportation. Annals of Operations Research, 222(1), 361–387.
doi pdf
github hazardous materials transportation; value-at-risk; social risk mitigation abstract
This paper introduces a Value-at-Risk (VaR) model to generate route choices for a hazmat shipment based on a specified risk confidence level. VaR is a threshold value such that the probability of the loss exceeding the VaR value is less than a given probability level. The objective is to determine a route which minimizes the likelihood that the risk will be greater than a set threshold. Several properties of the VaR model are established. An exact solution procedure is proposed and tested to solve the single-trip problem. To test the applicability of the approach, routes obtained from the VaR model are compared with those obtained from other hazmat objectives, on a numerical example as well as a hazmat routing scenario derived from the Albany district of New York State. Depending on the choice of the confidence level, the VaR model gives different paths from which we conclude that the route choice is a function of the level of risk tolerance of the decision-maker. Further refinements of the VaR model are also discussed.
- Berglund, P. G. and C. Kwon (2014). Solving a Location Problem of a Stackelberg Firm Competing with Cournot-Nash Firms. Networks and Spatial Economics, 14(1), 117–132.
doi pdf Location Analysis; Stackelberg-Cournot-Nash Equilibrium; Game Theory; Variational Inequality; Simulated Annealing
abstract
We study a discrete facility location problem on a network, where the locating firm acts as the leader and other competitors as the followers in a Stackelberg-Cournot-Nash game. To maximize expected profits the locating firm must solve a mixed-integer problem with equilibrium constraints. Finding an optimal solution is hard for large problems, and full-enumeration approaches have been proposed in the literature for similar problem instances. We present a heuristic solution procedure based on simulated annealing. Computational results are reported.
- Kang, Y., R. Batta and C. Kwon (2014). Generalized Route Planning Model for Hazardous Material Transportation with VaR and Equity Considerations. Computers & Operations Research, 43, 237–247.
doi pdf
github Value-at-Risk; multi-trip hazmat transportation; social risk mitigation; risk equity; dissimilar path abstract
Recently, the Value-at-Risk (VaR) framework was introduced for the routing problem of a single hazmat trip. In this paper, we extend the VaR framework in two important ways. First, we show how to apply the VaR concept to a more realistic multi-trip multi-hazmat type framework, which determines routes that minimize the global VaR value while satisfying equity constraints. Second, we show how to embed the algorithm for the single hazmat trip problem into a Lagrangian relaxation framework to obtain an efficient solution method for this general case. We test our computational experience based on a real-life hazmat routing scenario in the Albany district of New York State. Our results indicate that one can achieve a high degree of risk dispersion while controlling the VaR value within the desired confidence level.
- Berglund, P. G. and C. Kwon (2014). Robust Facility Location Problem for Hazardous Waste Transportation. Networks and Spatial Economics, 14(1), 91–116.
doi pdf Location problem; Hazardous waste facility; Robust optimization; Genetic algorithm
abstract
We consider a robust facility location problem for hazardous materials (hazmat) transportation considering routing decisions of hazmat carriers. Given a network and a known set of nodes from which hazmat originate, we compute the locations of hazmat processing sites (e.g. incinerators) which will minimize total cost, in terms of fixed facility cost, transportation cost, and exposure risk. We assume that hazmat will be taken to the closest existing processing site. We present an exact full enumeration method, which is useful for small or medium-size problems. For larger problems, the use of a genetic algorithm is explored. Through numerical experiments, we discuss the impact of uncertainty and robust optimization in the hazmat combined location-routing problem.
- Ahmed, M. T. and C. Kwon (2014). Optimal Contract-Sizing in Online Display Advertising for Publishers with Regret Considerations. Omega, 42(1), 201–212. doi
pdf Newsboy problem; Operations management; Risk abstract
In this paper, we study optimal contract problems for online display advertisements with pay-per-view pricing scheme. We first provide and analyze a single contract model, which is shown to be equivalent to the newsvendor problem. We then consider a stochastic optimization problem with two different advertisements and show that a contract to display both of them is not optimal for a risk-neutral publisher. However, we show that a contract to display of both advertisements may be optimal when we consider the risk attitude of the publisher. Numerical experiments illustrate the change of optimal strategy for different risk levels.
- Toumazis, I. and C. Kwon (2013). Routing Hazardous Materials on Time-Dependent Networks using Conditional Value-at-Risk. Transportation Research Part C: Emerging Technologies, 37,
73–92. doi pdf
github dynamic shortest path; time-dependent network; conditional value-at-risk; hazardous materials transportation abstract
We propose a new method for mitigating risk in routing hazardous materials (hazmat), based on the conditional value-at-risk (CVaR) measure, on time-dependent vehicular networks. The CVaR models are shown to be flexible and general routing models for hazmat transportation, and can be solved efficiently. This paper extends the previous research by considering CVaR for hazmat transportation in the case where accident probabilities and accident consequences are time-dependent. We provide a numerical method to determine an optimal departure time and an optimal route for a given origin-destination pair. The proposed algorithm is tested in a realistic road network in Buffalo, NY, USA and the results are discussed.
- Kwon, C., T. Lee, P. G. Berglund (2013). Robust Shortest Path Problems with Two Uncertain Multiplicative Cost Coefficients. Naval Research Logistics, 60(5), 375–394.
doi pdf
github robust shortest path; budgeted uncertainty; hazardous materials transportation abstract
We consider a robust shortest path problem when the cost coefficient is the product of two uncertain factors. We first show that the robust problem can be solved in polynomial time by a dual variable enumeration with shortest path problems as subproblems. We also propose a path enumeration approach using a $K$-shortest paths finding algorithm that may be efficient in many real cases. An application in hazardous materials transportation is discussed and the solution methods are illustrated by numerical examples.
- Ahmed, M.T. , and C. Kwon (2012). Pricing Game of Online Display Advertisement Publishers. European Journal of Operational Research, 219, 477-487.
doi pdf online display advertising; optimal pricing; Nash equilibrium; newsvendor problem
abstract
We consider an online display advertisement publisher who maximizes the revenue by optimal pricing in an oligopoly setting. Each publisher interacts with others though setting cost-perimpression (CPM) that affects the demand for everyone. Using the pseudoconcavity of the objective function, we study the best response of the publisher while her strategy space changes. We also consider the sensitivity of the publisher while other publishers changes their CPM. In both cases, the best response of the publisher depends entirely on her current best response CPM. We provide an algorithm for finding the equilibrium and illustrate by numerical examples.
- Srinivasan, A. and C. Kwon (2012). Operations of Online Advertising Services and Publisher's Option. Journal of the Operational Research Society, 63, 674–682.
doi pdf online advertising; Nash bargaining game; option contract
abstract
We analyse the use of options for online advertisement publishers. By providing a discount or rewards to advertisers, publishers can utilize their uncertain service capacity, page-views, more efficiently. We use Generalized Nash Bargaining to study the feasibility of the option contract and solve for an optimal value for the option price. We compare the revenues and benefits from advertisements under the option contract, with those without the options using numerical studies. We also study the impact of pricing and other components in the game on the optimal option price, the publisher's revenues, and the advertiser's benefits from the advertisements.
- Chung, B.D., J. Li, T. Yao, C. Kwon and T. L. Friesz (2012). Demand Learning and Dynamic Pricing under Competition in a State-Space Framework. IEEE Transactions on
Engineering Management, 59(2), 240–249. doi
pdf Competition, demand learning, differential variational inequality, dynamic pricing, Markov chain Monte Carlo, nonlinear time series abstract
In this paper, we propose a revenue optimization framework integrating demand learning and dynamic pricing for firms in monopoly or oligopoly markets. We introduce a state-space model for this revenue management problem, which incorporates game-theoretic demand dynamics and nonparametric techniques for estimating the evolution of underlying state variables. Under this framework, stringent model assumptions are removed. We develop a new demand learning algorithm using Markov chain Monte Carlo methods to estimate model parameters, unobserved state variables, and functional coefficients in the nonparametric part. Based on these estimates, future price sensitivities can be predicted, and the optimal pricing policy for the next planning period is obtained. To test the performance of demand learning strategies, we solve a monopoly firm's revenue maximizing problem in simulation studies. We then extend this paradigm to dynamic competition, where the problem is formulated as a differential variational inequality. Numerical examples show that our demand learning algorithm is efficient and robust.
- Wang, J., Y. Kang, C. Kwon and R. Batta (2012). Dual Toll Pricing for Hazardous Material Transport with Linear Delay. Networks and Spatial Economics, 12, 147–165.
doi pdf hazardous materials; toll pricing; congestion; risk
abstract
In this paper, we propose a dual toll pricing method to mitigate risk of hazardous materials (hazmat) transportation. We aim to simultaneously control both regular and hazmat vehicles to reduce the risk. In our model, we incorporate a new risk measure to consider duration-population-frequency of hazmat exposure. We first formulate the model as a Mathematical Program with Equilibrium Constraints (MPEC). Then we decompose the MPEC formulation into first-stage and second-stage problems. Separate methods are developed to solve each stage. A numerical example is provided and possible extensions are discussed.
- Jung, T. and C. Kwon (2011). Retailer-Supplier Matching: an Application of the Deferred Acceptance Algorithm. International Journal of Services Operations and Informatics, 6(3),
248–258. doi pdf
abstract
In this paper, we apply matching theory to supply chain coordination. We present mathematical optimization models similar to the newsvendor problem to provide appropriate conditions for retailer-supplier matching. In particular, our matching algorithm, compared to the general matching theory, has uniquely been affected by contract sizes and ordering sequences. We also study that our matching application guarantees stable and optimal outcomes. Numerical examples with various parameter settings are provided to test the feasibility of the matching algorithms. We find that we can avoid the worst matching case when we use the proposed matching algorithms.
- Friesz, T. L., T. I. Kim, C. Kwon and M. A. Rigdon (2011). Approximate Network Loading and Dual Time Scale Dynamic User Equilibrium. Transportation Research
Part B: Methodological, 45(1), 176-207. doi
pdf dynamic user equilibrium; differential variational inequalities; differential algebraic equations; dual-time-scale; fixed-point algorithm in Hilbert space abstract
In this paper we present a dual-time-scale formulation of dynamic user equilibrium (DUE) with demand evolution. Our formulation belongs to the problem class that Pang and Stewart (2008) refer to as differential variational inequalities. It combines the within-day time scale for which route and departure time choices fluctuate in continuous time with the day-to-day time scale for which demand evolves in discrete time steps. Our formulation is consistent with the often told story that drivers adjust their travel demands at the end of every day based on their congestion experience during one or more previous days. We show that analysis of the within-day assignment model is tremendously simplified by expressing dynamic user equilibrium as a differential variational inequality. We also show there is a class of day-to-day demand growth models that allow the dual-time-scale formulation to be decomposed by time-stepping to yield a sequence of continuous time, single-day, dynamic user equilibrium problems. To solve the single-day DUE problems arising during time-stepping, it is necessary to repeatedly solve a dynamic network loading problem. We observe that the network loading phase of DUE computation generally constitutes a differential algebraic equation (DAE) system, and we show that the DAE system for network loading based on the link delay model (LDM) of Friesz et al. (1993) may be approximated by a system of ordinary differential equations (ODEs). That system of ODEs, as we demonstrate, may be efficiently solved using traditional numerical methods for such problems. To compute an actual dynamic user equilibrium, we introduce a continuous time fixed-point algorithm and prove its convergence for effective path delay operators that allow a limited type of nonmonotone path delay. We show that our DUE algorithm is compatible with network loading based on the LDM and the cell transmission model (CTM) due to Daganzo (1995). We provide a numerical example based on the much studied Sioux Falls network.
- Moon. Y. and C. Kwon (2011). Online Advertisement Service Pricing and an Option. Electronic Commerce Research and Applications, 10(1), 38-48.
doi pdf online advertisements, option contract, Nash bargaining, click-through rate, utility maximization
abstract
For the Internet advertisement market, we consider a contract problem between advertisers and publishers. Among several ways of pricing online advertisements, the methods based on cost-per-impression (CPM) and cost-per-click (CPC) are the two most popular. The CPC fee is proportional to the click-through rate (CTR), which is uncertain and makes decisions of advertisers and publishers difficult. In this paper, we suggest a hybrid pricing scheme: advertisers pay the minimum of CPM and CPC fees by purchasing an option from publishers. To determine the option price, we consider a Nash bargaining game for negotiation between an advertiser and a publisher and provide the solution. Further, we show that such option contracts will help the advertiser avoid high cost and the publisher generate more revenue. The option contract will also improve the contract feasibility, compared to CPM and CPC.
- Kwon, C. (2011). Single-Period Balancing of Pay-Per-Click and Pay-Per-View Online Display Advertisements. Journal of Revenue and Pricing Management, 10(3), 261-270.
doi pdf online advertising; display advertisements; cost-per-impression; cost-per-click; click-through-rate; web publisher
abstract
In this article, we study a balancing problem of web publishers for pay-per-view and pay-per-click contracts for online display advertising. Considering the details of contracts, we refine prior research results on the recommendation of optimal strategies. We examine the problem by formalizing a simple stochastic optimization problem for a single period of advertising contracts. We investigate how pricing and other contract components will affect the optimal display strategies analytically and numerically.
- Kwon, C., T. L. Friesz, R. Mookherjee, T. Yao and B. Feng (2009). Non-cooperative Competition Among Revenue Maximizing Service Providers with Demand Learning. European Journal of
Operational Research, 197(3), 981-996. doi
pdf Revenue management, Pricing, Demand learning, Differential games, Kalman filters abstract
This paper recognizes that in many decision environments in which revenue optimization is attempted, an actual demand curve and its parameters are generally unobservable. Herein, we describe the dynamics of demand as a continuous time differential equation based on an evolutionary game theory perspective. We then observe realized sales data to obtain estimates of parameters that govern the evolution of demand; these are refined on a discrete time scale. The resulting model takes the form of a differential variational inequality. We present an algorithm based on a gap function for the differential variational inequality and report its numerical performance for an example revenue optimization problem.
- Kwon, C. and T. L. Friesz (2008). Valuation of American Options by the Gradient Projection Method. Applied Mathematics and Computation, 206(1), 380-388.
doi pdf American options, variational inequalities, gradient projection
abstract
We study an equivalent optimization problem with an inequality constraint and boundary conditions, whose necessary condition for optimality is the variational inequality presentation of American options. To solve the problem, we use the gradient projection method, with discretizations both in time and space. We tested the algorithm and compared with the projective successive over-relaxation method.
- Friesz, T. L. and C. Kwon (2008). Supply Chain Design in Perfect Competition. International Journal of Services Operations and Informatics, 3(3/4),
340-356. doi pdf
abstract
In this paper, we apply the theory of optimal control and theory of traffic assignment for supply chain design in perfect competition. We model the time staging and generalised routing of input factors needed for production by a firm. The production process will typically involve several stages, and as such is described by paths through a production network whose nodes are the various stages of production. We develop an algorithm and test it for a small numerical example.
- Miller, T. C., T. L. Friesz, R. L. Tobin and C. Kwon (2007). Reaction Function Based Dynamic Location Modeling in Stackelberg-Nash-Cournot Competition. Networks and Spatial Economics, 7(1),
77-97. doi pdf Dynamic Stackelberg equilibrium location modeling, reaction functions
abstract
We formulate a dynamic facility location model for a firm locating on a discrete network. It is assumed that this locating firm will act as the leader firm in an industry characterized by Stackelberg leader-follower competition. The firm's I competitors are assumed to act as Cournot firms and are each assumed to operate under the assumption of zero conjectural variation with respect to their I-1 Cournot competitors. Using sensitivity analysis of variational inequalities within a hierachical mathematical programming approach, we develop reaction function based dynamic models to optimize the Stackelberg firm's location decision. In the second half of this paper, we use these models to illustrate through a numerical example the insights yielded by our approach.