previous day
all days

View: session overviewtalk overview

09:00-10:30 Session 10A
Location: Regents Hall
A simulation-based optimization algorithm for dynamic traffic control problems
SPEAKER: unknown

ABSTRACT. This work presents a first step towards using stochastic microscopic traffic simulators to address dynamic urban transportation problems. Past work has developed simulation-based optimization techniques that can solve static transportation problems in a highly computationally efficient manner. This existing framework achieves efficiency through the combined use of simulated information with information from an analytical and tractable traffic model. The information is combined into what is known as a metamodel. The analytical traffic model combines ideas from traditional urban traffic models with ideas from finite capacity queueing network theory. It is a differentiable and highly tractable model yet is based on stationarity assumptions. That is, it yields time-invariant approximations of the distributions of the main network performance metrics.

This paper proposes a metamodel that combines information from the simulator with information from a time-dependent analytical traffic model. The main challenge is to analytically approximate the resulting temporal evolution of traffic states, while remaining tractable, such that the SO framework remains computationally efficient.

This paper first formulates the dynamic analytical traffic model. The latter is then used as part of a metamodel to perform dynamic simulation-based optimization. The dynamic queueing network model is built on an extension of an analytical and highly tractable yet stationary queueing network model recently proposed. The latter model has allowed us to address large-scale simulation-based signal control problems. In the queueing model, each lane of an urban road network is represented as a queue. The model analytically approximates the between-queue interactions of sequential lanes (i.e. how a lane interacts with its directly upstream and downstream lanes).

The use of the proposed metamodel SO framework will be illustrated and evaluated with case studies based on the road network of the Swiss city of Lausanne. A microscopic simulation model of Lausanne city center that has been calibrated for evening peak period demand is used in this project. We solve traditional signal control problems for the full city of Lausanne (over 600 links and 200 intersections). We use the initial existing SO algorithm that resorts to a derivative-free trust region (TR) algorithm. We embed and compare the performance of the following types of metamodels within this SO algorithm: 1) traditional metamodels (e.g. a polynomial) 2) time-invariant analytical traffic models (e.g. stationary queueing network model), 3) time-dependent analytical traffic model (i.e. proposed approach). We compare their performance as follows. Firstly, we use each metamodel to address a fixed-time signal control problem. We compare the city-wide performance of the derived signal plans. Secondly, we solve a traffic responsive signal control problem using the proposed approach. We present and discuss the benefits as well as potential drawbacks of using an analytical dynamic traffic model as a metamodel.

SPEAKER: unknown

ABSTRACT. Uncertainty is a fundamental property of transportation networks which evolve continually due to varying travel demand, traffic capacity, or individual behaviour. Over the past few years, the concept of strategic scenario based traffic assignment has emerged as a promising method to systematically incorporate these uncertainties into transport models (Hamdouch et al., 2004; Marcotte et al., 2004; Waller et al., 2013; Dixit et al., 2013). In strategic traffic assignment, the travel demand is modelled as a random variable which can take a finite number of values (scenarios), where each scenario corresponds to a representation of the network state. Hence in a strategic traffic assignment, users minimize their expected travel time while recognizing the underlying probability distribution for the scenarios and the network travel times in each scenario. A strategic dynamic traffic assignment problem requires that users be able to find the Shortest Path (SP) in a time-dependent network across a set of stochastic demand scenarios. Whilst efficient procedures exist to find optimal routes in deterministic and/or time-invariant environments (Dijkstra, 1959; Dreyfus, 1969; Frank, 1969), the same algorithms cannot always provide optimal solutions in stochastic, time-dependent networks efficiently. This work seeks to address this gap by finding the Stochastic Scenario-based Time-Dependent Shortest Path (SSTDSP) across a set of stochastic scenarios, where time-dependent arc costs are known in each scenario.

Due to the time-varying nature of transit systems and highways, the SP variant where arc costs represent travel times which depend on the time of arrival at the tail of the arc has attracted the attention of many researchers in the field of transportation science. Dreyfus (1969) was the first to observe that Dijkstra’s algorithm (1959) could be used to solve the Time-Dependent Shortest Path (TDSP) with the same (polynomial time) complexity, given an optimal waiting policy at intermediate nodes: such waiting policy assumes that a traveller will always wait for the departure time which provides the earliest arrival time at the next node. However, the relaxations of this assumption has a severe impact on the complexity of the TDSP algorithms as observed by Orda and Rom (1990), which explored the role of delay (travel time) functions on arcs and different waiting policies. In particular, the TDSP is known to be a NP-hard problem if the network is not First-In First-Out (FIFO) and if the waiting policy is not optimal (Sherali et al. 1998). Furthermore, the case where delay functions are continuous may potentially result in a non-polynomial complexity of the TDSP problem in FIFO networks. This result was recently proven for piecewise linear delay functions by Foschini et al. (2011) who settled a conjecture established by Dean (2004).

If the network is assumed time-invariant, one may find the stochastic SP by simply determining the expected cost of each arc in the network and using a generic SP algorithm with the obtained arc costs (Frank, 1969). In this context, Waller and Ziliaskopoulos (2002) showed that polynomial time recourse algorithms can be obtained in the case where arc costs exhibit a limited spatial and/or temporal dependency. In contrast, the Stochastic Time Dependent Shortest Path (STDSP) was first studied by Hall (1986) who showed that this procedure cannot always find the least expected time path in stochastic, time-dependent networks. Psaraftis and Tsitsiklis (1993) studied a variant of the STDSP where the state of successive arcs are revealed upon arrival at a node and consider a routing policy where waiting time at nodes is permitted but penalized. They were able to obtain efficient algorithms given the assumption that the network is acyclic.

Miller-Hooks and Mahmassani (1998) investigated a more general case of this problem with no assumptions regarding the network FIFO property or waiting policies, and established an efficient algorithm to find the least possible time path in stochastic, time-dependent networks. However, by choosing the least arc cost at every node they ignored the impact of the conditionality of the state probabilities of travel times. Addressing this particular issue, Miller-Hooks and Mahmassani (2000) provided an optimal procedure to find the least expected time path, and introduced the notion of label dominance for stochastic, time-dependent networks. In order to ensure global optimality, the proposed algorithm must maintain an arbitrarily large but finite list of non-dominated labels at each node of the network. As the number of non-dominated labels at a node can grow exponentially (depending on the number of paths travelling through the node of interest), the aforementioned algorithm has a non-polynomial time complexity. Miller-Hooks (2001) also investigated the adaptive case, where arc cost information are revealed at the arrival at intermediate nodes and proposed an efficient algorithm for this variant. A thorough comparison of a priori and online routing policies in non-FIFO networks is provided in Miller-Hooks and Mahmassani (2003). A review of the online routing variants in stochastic, time-dependent networks is provided by Gao and Chabini (2006) who propose a two-dimensional taxonomy of STDSP problems according to arc cost dependency and information access. Their findings confirm that the assumptions in the modelling of stochastic, time-dependent networks can have a significant impact on the computational efficiency of routing algorithms.

This study investigates the efficiency of routing algorithms in stochastic, time-dependent networks with respect to different probability structures on arc costs as well as different node waiting policies. The main contribution of this work is to characterize the SSTDSP, which is a variant of the STDSP problem where time-dependent arc costs are organized by scenarios, and each scenario has an associated probability of occurrence. In the context of scenario-based routing, we show the existence of computationally efficient lower and upper bounds on the number of non-dominated labels at a node and propose an algorithm for the SSTDSP problem. We also build on the existing literature and show the implication of various waiting policies on the computational complexity of the algorithms for the STDSP. In particular, we derive sufficient conditions on waiting policies for the establishment of polynomial time algorithms for the STDSP and illustrate their impact on a case study. The algorithmic solutions obtained can be used to solve the aforementioned strategic dynamic traffic assignment problem in a computationally tractable manner and provide a novel approach to study strategic routing decisions in transportation networks.

09:00-10:30 Session 10B
Location: Beane Hall
A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times
SPEAKER: unknown

ABSTRACT. We consider the vehicle routing problem with hard time windows and stochastic service times (VRPTW-ST) which appears in various practical applications where the drivers (e.g., technicians or repairmen) of the vehicles perform specific services at the visited customers. The central issue is to determine vehicle routes that respect the customer's time windows when the details of the service to be performed at each customer are unknown beforehand, yielding stochastic service times. We propose to study this problem as an a priori optimization problem that involves two stages. In the first stage when service times are unknown, a set of planned routes is computed. In the second stage, these routes are modified according to a given recourse policy. Two recourse policies based on skipping customers are studied. The objective is to minimize the total expected travel cost, including the expected costs of the recourse actions. We formulate this problem as a set partitioning problem and develop an exact branch-price-and-cut algorithms for solving it. Computational results show that our methods are able to efficiently solve instances with up to 50 customers for both recourse policies.

A one-warehouse, multi-newsvendor distribution systems with resupply and vehicle routing
SPEAKER: unknown

ABSTRACT. We study a problem that is inspired by a real-world application of delivering perishable products (e.g. milk, bread, meat) from a retailer to outlets. Due to their short shelf-life, perishable products pose a challenge for finding the balance between the costs of over- and understock. The majority of literature on the newsboy problem assumes that the products can only be ordered once, i.e. for the beginning of the replenishment period. However, in the real world, for many products there exists an opportunity to place a second order during this period. If the realized demand is low, a smaller initial order followed by an additional order later in that period reduces losses.

The aim of our work is to consider the opportunity to partly postpone decisions after some additional information has revealed, i.e. by including the option for placing the second delivery order later in the replenishment period. As there are typically several outlets that are served by the same vehicle, inventory and routing decisions have to be taken in an integrated way. Therefore, the purpose of our model is to address several issues: We need to determine the time point when the second delivery has to take place, to assign outlets to the given routes and to find the sequence in which they are going to be visited, and to decide about the sizes of delivery quantities for the first and the second order for each outlet.

The time point when the vehicle starts the second delivery is decided upfront. The vehicle starts the tour with initial load. For the sake of simplicity, we assume that there is always enough capacity in the vehicle. The vehicle arrives at each outlet at a certain time point, which is adjusted to fit each outlet based on their expected inventory level. After arriving at the outlet, the actual remaining inventory level can be observed. We assume, that at this time point, the inventory of all outlets still to be visited subsequently on the same tour is not known. The decision regarding the size of the second delivery is made based on the inventory level probability distribution of the following outlets, the initial shipment to this outlet and the remaining stock on the vehicle. When the truck arrives at the last outlet of a tour, all remaining stock on the truck will be assigned to this outlet. From the requirements of the inventory model, it is obvious that the shipments to each outlet are dependent on the sequence in which customers are visited on a tour. Therefore it is necessary to find the best way to formulate the routing problem and to use appropriate algorithms to solve the problem.

The inventory allocation problem is solved by standard stochastic dynamic programming using backward recursion. We start by determining the allocation for the last outlet on the tour, which is equal to the remaining stock on the vehicle. For all other outlets, an item is assigned in the way, that the chance that a stockout at the current outlet is prevented is equal to the chance of preventing a stockout at the pool of succeeding outlets in the tour. The initial loading quantity for the second delivery is selected by maximizing the profit at the first outlet. The timing of the second delivery for each outlet is optimized by using numerical search.

We can observe two notions that derive from our approach. The first is the additional benefit when outlets are visited at their computed optimal time point and the second is the profit which is achieved by minimizing the risk through customer pooling. Therefore, when it comes to routing part of the problem, we use two different formulations: a single vehicle and multi vehicle mode. The first formulation might fit companies that have densely located customers which expect low demand. Through this formulation, we investigate the effect of risk pooling by allocating the load to large number of outlets, whereas in the latter formulation we oppose the benefit achieved through pooling to the additional profit achieved when, with the help of having more vehicles, outlets can be visited closer to their optimal timing. The objective of both models is to maximize the profit achieved during the first and the second delivery. The profit is reduced by the travel costs which result from the second delivery. The costs for the first delivery for the beginning of the period do not have any influence on our problem and are therefore omitted from consideration. For handling the routing decisions, we use algorithms that are inspired by ideas of Variable Neighborhood Search.

For the purpose of testing the performance of our algorithm, we generated a set of numerical problems based on benchmark data from the literature. We assume that demand follows a stochastic distribution and introduce a tractable demand model based on a Compound Renewal process. The numerical results show that the profit significantly increases when a second delivery is allowed.

Avoiding Lateness in Routing Problems with Time Windows and Stochastic Travel Times
SPEAKER: unknown

ABSTRACT. (see attachment for abstract)

10:45-12:15 Session 11A
Location: Regents Hall
Same Day Delivery for Online Purchases
SPEAKER: unknown

ABSTRACT. Where instant gratification was once the largest advantage of brick-and-mortar stores over online retailers, same day delivery now brings near instant gratification to online shoppers. “There’s lots going on in this space, and it’s all driven by Amazon,” says Tom Allason, founder and chief executive of Shutl, a British same day delivery service that expanded to the U.S. in 2013 (Clifford and Miller, 2013). Allason predicts, however, that as soon as consumers know that same day delivery is available, they will start to expect it and demand it. Same day delivery for online purchases is a rising trend being embraced by Amazon, Walmart, eBay, Google, and a handful of recent internet start-ups.

Same day delivery, however, is a logistically complicated and expensive service to operate. Despite the challenge of same day delivery and it’s growing use, there is no academic literature that directly addresses the problem. We introduce a dynamic pick-up and delivery problem with deadlines that incorporates key features associated with same day delivery logistics.

The problem is characterized by a fleet of vehicles operating from a central depot and by a set of geographic regions with known arrival rates of delivery requests. Arrival rates of delivery requests depend on both the region and the time of day. Each region may represent an individual customer or an aggregation of customers. For example, in a city scenario customers may be aggregated by city blocks. Multiple requests may arrive from the same region. Associated with each delivery request is a delivery deadline that becomes known at the time of request. For example, a deadline might specify that a request must be fulfilled within three hours. The objective is to maximize the expected number of fulfilled requests. One of the key challenges with the same day delivery problem is that there are many options as to how the routing of these deliveries can occur. These options include which packages to load onto which vehicle, when a vehicle should wait at the depot or a customer location, when a vehicle should return to the depot, and which customer should be visited next. As a result, we are challenged not only by the traditional curse of dimensionality associated with a large state space, but also with a curse of dimensionality around the actions.

In the initial stages of this research, we examined two different versions of the problem. In one version, each vehicle was assigned a fixed delivery zone. In the second version, the restriction of delivery zones was relaxed. In both versions of the problem, vehicle waiting was only permitted at the depot and results were obtained for homogeneous delivery deadlines of one, two, and three hours. We compared the situation where vehicles leave the depot immediately upon receiving a request (early departure) to the situation where vehicles leave the depot at the latest time such that all accepted requests are able to be fulfilled by their deadlines (late departure). In both cases, longer deadlines increase the number of requests that can be fulfilled and early departures and late departures allow an approximately equal number of requests to be fulfilled. However, the early departure is desirable because the average time a customer has to wait for his delivery is lower. Also, relaxing the restriction of delivery zones increases the number of requests that can be fulfilled and decreases the average customer wait time compared to the zone restricted case. These results confirm intuition and previous results in the literature. We also completed a break-even cost analysis that incorporates fuel costs and the hourly cost of wages.

One weakness of our initial work is that it does not explicitly incorporate information about future requests. In this work, we develop a solution approach that accounts for future demand. This is crucial in making good routing decisions about which packages to load onto which vehicle, where to go next, and when to wait at a location. To incorporate information about future requests, we develop a sample scenario approach. In such an approach, samples of future requests are generated from request arrival rate distributions. This information is combined with the current known requests to create vehicle routes for each scenario. Then, future requests are removed from each of the routes in each scenario, and a consensus function is used to select the routes that are most similar to the routes in each other scenario. One challenge with this method is sample generation because samples must contain requests that can be fulfilled before their deadlines. A second challenge arises because the sample scenario approach cannot account for pre-emptive returns to the depot or decisions of when and where to wait. We present our sample scenario framework and computational experiments that demonstrate the benefits of the sample scenario approach compared to our initial experiments that do not incorporate stochastic information.

References Clifford, S. and Miller, C. C. (2013). Instantly yours, for a fee. The New York Times, page B1. December 28.

Time-Dependent Routing Problems with Path Flexibility in Mega-City Logistics
SPEAKER: unknown

ABSTRACT. This paper deals with advanced vehicle routing problems in mega-cities. To adequately reflect the influence of road traffic conditions, which are both time and region dependent, on the vehicle routing decisions (to visit customers requiring services), we combine a time-dependent vehicle routing problem with a time-dependent shortest path problem (TD-SPP). Specifically, we develop a Vehicle Routing Problem based on the Pollution-Routing Problem (PRP), first coined by Bektas and Laporte (2011). We emphasize the importance of decoupling the customer graph (with customer locations as nodes in the network) and the underlying, more detailed, geographical graph (with intersections as nodes in the road network), especially in time-dependent vehicle routing. We integrate the TD-SPP and TD-PRP into a joint framework. Specifically, we jointly consider optimizations in customer routing on the customer graph and flexible path selection between each O-D pair on the geographical graph, taking time-dependent road traffic condition into account. As such, the true driver of cost saving in smart routing in the TD-PRP comes from the flexible time-dependent path choices in the TD-SPP. Furthermore, we investigate on the benefit of path flexibility under uncertain traffic condition of the road network with a two-stage stochastic mixed integer program. We construct a case study based on the real road network of Beijing metropolitan area and historical traffic data. Numerical results demonstrate the significance of cost saving by decoupling the customer graph and the underlying geographical graph in route planning as well as the cost saving by decoupling the offline routing decision and the en route path selection decision. We also examine the impact of flexibility in the departure time at the depot and in the allowable waiting time at customer locations, which can be region-dependent.

Managing Decentralized Resource Sharing in Carrier Alliances under Demand Uncertainty
SPEAKER: unknown

ABSTRACT. In the transportation industry, resource sharing is a common collaborative strategy used in the carrier alliances where the member companies pool fleets and integrate service networks. While resource sharing has the potential to create synergistic value, realizing this value can be challenging at the operational level, as individual companies manage their resources aiming to increase their own benefits even in an alliance. In practice, this challenge is often addressed by resource sharing agreements that impose operational mechanisms to coordinate individual incentives and decisions. A major practical complexity in designing such an agreement is the uncertainties in demand and the associated information asymmetry between the mechanism designer and the alliance members. In particular, in carrier alliances, collaboration and resource sharing policies are often determined as tactical decisions before operations start. Hence, in this research, we study designing a market-based capacity exchange mechanism that is robust to demand uncertainties, i.e., can effectively coordinate resource sharing under a set of potential demand scenarios using fixed exchange prices. Our analysis provides insights into the link between the robustness of the capacity exchange mechanism and the structure of the integrated service network of the carrier alliance. Based on these findings, we propose pricing strategies and other mechanism design approaches to promote the robustness of resource sharing agreements based on capacity exchanges.

10:45-12:15 Session 11B
Location: Beane Hall
Integrating Resource Acquisition and Repositioning Into Tactical Transportation Planning Under Uncertainty
SPEAKER: unknown

ABSTRACT. Please see PDF

Stochastic Capacity Expansion with Multiple Sources of Capacity for Transportation Networks
SPEAKER: unknown

ABSTRACT. Capacity expansion is mainly concerned with the optimal time and amount of capacity acquisition, and the optimal capacity allocation. Capacity expansion models can be found in a wide range of applications in transportation networks, which usually involves significant capital investments, uncertainties in the future forecasts, and long time horizon. In this research, we consider capacity expansion of transportation networks under uncertainty, using multi-stage stochastic programming approach.

The models in network capacity expansion often assume that there is only one source of capacity available for acquisition. This capacity is purchased and permanently owned by the decision maker and we call it the permanent capacity. However, in practice, there could be other sources of capacity. In this research, we introduce two other commonly used sources of capacity besides the permanent capacity, i.e., the spot market capacity and the contract capacity. Spot market capacity refers to the capacity that can only be purchased and used in the current period, while contract capacity refers to the capacity that is available in the current period, only if a contract has been signed for it in previous periods. Spot market capacity is most suitable when forecasting error or unexpected disruption happens. Contract capacity is used when the future uncertainty is relatively predictable, and the decision maker does not plan to own the capacity in the long run. It is noteworthy that the decision for spot market capacity acquisition will be made after the random data is realized in each period, while the decision for contract capacity acquisition will be made before the random data is realized. Also, our model can capture the case where the decision maker signs contracts for arbitrary numbers of periods. Examples include hiring seasonal workers, signing a contract to lease an aircraft for a month, and using spot market and contracted fleets by trucking companies. All our models are based on multi-stage stochastic programming, using a scenario tree with finite number of nodes (N) to represent the random data.

Firstly, we study the single resource capacity expansion problem. We show the problem is polynomially solvable and develop efficient primal and dual algorithms to solve it. We prove the optimality of the algorithms and show that their complexities are O(N2) and O(NlogN), respectively.

Secondly, we introduce a general transportation network, and assume that permanent capacity, spot market capacity, and contract capacity are available for nodes and arcs of the network. Specially, the transportation decisions are modeled in the context of a min cost flow network, and the capacity decisions are integers, which leads to an NP-hard problem. We first assume that there is no budget constraint for the capacity acquisition decisions. To solve the non-budget case, we study the decomposition nature of the problem and design an asymptotically convergent approximation algorithm, which separates the original problem into single resource capacity expansion problems, and independent min cost network flow problems. The former can be solved using the polynomial algorithms for the single resource models, and the latter can be solved by efficient network flow algorithms.

Thirdly, we define the budget case of the transportation network capacity expansion problem by imposing a budget on the permanent capacity acquisition cost. In the budget case model, the decomposition algorithm for the non-budget case does not work. We propose a Lagrangian relaxation method to solve the problem, which relaxes the budget constraint. We design efficient upper bound construction procedures to speed up this algorithm.

Finally, we present numerical experiments for both cases. For the non-budget case, we compare the solution time of CPLEX with that of our approximation algorithm. For real-life sized problems, the approximation algorithm solution times is within at most 2% of CPLEX solution times, while keeping the optimality gap under 1%. For budget case, The Lagrangian relaxation algorithm can significantly reduce the solution time, while keeping the optimality gap within 3%.

In the future work, we will consider the capacity expansion of a transportation network in the context of multi-commodity network flow, which has wide applications in transportation, e.g., the railway blocking problem.

Distributionally Robust Multi-Commodity Network Design Problems under Demand Ambiguity
SPEAKER: unknown

ABSTRACT. Network design problems (NDPs) are commonplace in the development of modern society. From the installation of cables by internet service providers, to the widening of roads by the government, NDPs play an important role in ensuring that organizations are able to meet demands from their clients while ensuring that they expend as little of their resources as they reasonably can. However, with the fluctuating demands of clients, it is in the best interest of these organizations to have a network design solution that is robust enough to cope with variability in client demand and keeps operational costs minimal.

In this paper, we examine such NDPs with uncertain demand. In particular, we focus on a multi-commodity NDP, with multiple commodities sharing common arc capacities in the network. The decision maker in this problem seeks to design the arc capacities on a network to meet the demands from his clients who reside in a subset of the nodes in the network. The design of arc capacities can either be binary (the arc either has some fixed capacity, or does not exist in the network) or continuous (the arc capacity can be any non-negative value), and are increased before the realization of demand; the flow on the arcs is decided after the realization of demand.

The total cost of modifying the network and flowing commodities will fluctuate depending on the realized value of demand. Yet, the true distribution of the demand is rarely known; therefore it is important to provide some robustness to the solution of the problem, so that the solution that is finally implemented by the decision maker does not violate any demand satisfaction constraints, regardless of the true distribution of demand. Specifically, the aim is to minimize the network design cost while ensuring solution robustness with respect to ambiguous demand distributions, under either an expectation-based or chance-constrained measure of the flow recourse.

Such a type of robustness that takes into account a set of feasible distributions of demand is known as distributional robustness. In general, distributionally robust stochastic programs (DRSPs) form a “middle ground” between stochastic programs and robust optimization problems: the former assumes full knowledge of the distribution of the uncertainty, which is often unrealistic; the latter only uses extreme events to determine the most conservative solution to a problem, whereas DRSPs seek solutions that “optimize” the worst-case outcome(s) with respect to all possible uncertainty distributions that can be described by a set of historical data samples, but do not require full knowledge of the distribution of the uncertainty.

Delage and Ye (2010) proposed a data-driven framework to solving DRSPs on a set that contains all distributions whose moments “match” the first and the second moments based on a set of data observations. They used Lagrangian dual approaches and reformulated DRSPs with convex constraints as semi-definite programs, or second-order cone programs in special cases, both of which are computationally tractable. Ben-Tal et al. (2013) studied DRSPs with linear constraints including random linear coefficients that follow an unknown distribution. By constructing divergence-function-based confidence sets of the ambiguous probability functions, a related DRSP can be reformulated as a tractable linear program using the conjugate function of some divergence function that is generally convex

In this paper, we will apply the approaches described by Delage and Ye (2010) and Ben-Tal et al. (2013) particularly to variants of the NDPs. As previously described, our formulations contain two stages, referring to as the first stage of planning arc capacities and the second stage of operating flows under uncertain node demands. The corresponding DRSPs seek a capacity design to minimize the maximum flow cost and/or demand losses that may occur for all possible probability distributions of the demand uncertainty restricted in the two types of confidence sets. For NDPs with continuous capacity design and objective functions of minimizing the expected cost, we directly apply the existing DRSP methods. We develop decomposition and cutting-plane algorithms for solving NDPs with 0-1 capacity design, as well as NDPs with chance constraints that bound the worst-case probability of the joint demand loss under ambiguous demand distributions.

In our computational studies, we test both randomized networks and fixed networks with randomized parameters. The random networks will be generated with a large number of nodes and with varying arc densities; the fixed networks will be based on the Sioux Falls road network, which has 24 nodes and 76 arcs. We will benchmark our DRSP approaches and solutions of solving the NDPs against their corresponding stochastic optimization and robust optimization formulation variants, and focus on comparing (i) the computational efficiency and (ii) the sensitivity of solutions to changes in parameters between the three approaches. We aim to demonstrate “the value of data” and insights of cost-and-risk tradeoff in various NDP variants under ambiguous demand.

[1] Delage, E. and Ye, Y. “Distributionally robust optimization under moment uncertainty with application to data-driven problems.” Operations Research, 58(3), 595-612, 2010.

[2] Ben-Tal, A. and Chung, B.D. and Mandala, S.R. and Yao, T. “Robust solutions of optimization problems affected by uncertain probabilities.” Management Science, 59(2), 341-357, 2013.

12:30-14:00 Session 12: Lunch
Location: Beane Hall
Disclaimer | Powered by EasyChair Smart Program