Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

SB08

5 - Advances in the Maximum K-cut Problem Vilmar Rodrigues de Sousa, Polytechnique, Montreal, QC, Canada, Miguel F. Anjos, Sebastien Le Digabel We consider the maximum k-cut problem that consists in partitioning the vertex set of a graph into k subsets such that the sum of the weights of edges joining vertices in different subsets is maximized. We present our recent computational advances using associated semidefinite and linear programming relaxations. n SB07 North Bldg 123 Joint Session OPT/Practice Curated: Transportation Network Analysis Sponsored: Optimization/Network Optimization Sponsored Session Chair: Ilke Bakir, Georgia Institute of Technology, Atlanta, GA, 30332, United States Co-Chair: Bahar Cavdar, Middle East Technical Univeristy, Ankara, 06800, Turkey 1 - Charm of Consistency - Two-stage Stochastic Team-orienteering Problem with Time Windows and Uncertain Services Requests Yongjia Song, Clemson University, 211 Fernow Street, 264 We consider a practical problem in transportation, where service providers serve a set of regular customers over a long-term horizon, and also receive requests from additional on-demand customers on a daily basis. We formulate this problem as a two-stage stochastic team orienteering problem, which is challenging for two reasons. First, on the first stage assignment decisions need to be made under incomplete information. Second, decisions on the second stage require to solve a deterministic team-orienteering problem with time windows. We address the two challenges via a progressive hedging framework integrating a runtime efficient heuristic, adapted version of the multiple scenario approach. 2 - An Integrated Fleet Management Model Introducing Alternative Fuel Trucks into Existing Diesel Fleets Ilke Bakir, University of Groningen, Groningen, Netherlands,, Alan Erera We address the challenge of introducing alternative fuel trucks into an existing fleet, while making necessary structural changes and maintaining feasible operations. We develop an integrated fleet management model, which incorporates (i) opening new maintenance facilities, and (ii) fleet deployment, into a fleet replacement framework. We demonstrate that the integrated model makes use of information that is often overlooked by conventional fleet replacement strategies. We propose a Benders’ decomposition framework and a Variable Neighborhood Search (VNS) algorithm for the integrated model; and demonstrate the performance of these methods with a comprehensive computational study. 3 - Service Network Design with Mixed Autonomous Fleets Yannick Oskar Scherr, Technische Universit t Braunschweig, Braunschweig, 38106, Germany, Bruno Albert Neumann- Saavedra, Mike Hewitt, Dirk C. Mattfeld We introduce a service network design problem that integrates automated driving technologies into the tactical planning of parcel delivery. In this problem, autonomous vehicles at SAE level 4 are only permitted to drive in dedicated zones for the sake of traffic safety. Outside of these zones, manually operated vehicles must guide them in platoons, i.e., groups of vehicles following each other closely. Our integer linear program not only decides on vehicle routes and delivery operations but also on the number of autonomous and manually operated vehicles. Results show different solution structures depending on the fleet configuration and increased complexity due to platooning. 4 - Sequential Optimization of the Intra-link Movement of an Emergency Response Vehicle Along Transportation Segments in the Connected Vehicle Environment Gaby Joe Hannoun, Virginia Tech, Blacksburg, VA, United States, Pamela Murray-Tuite, Kevin Heaslip, Thidapat Chantem The ERVs face numerous safety hazards in their attempts to reach their destinations in a timely manner. An integer linear program (ILP) was previously developed to delineate the fastest intra-link ERV path and to determine the optimal assignment location of each downstream vehicle. Since the ILP is not scalable on large links, we present a dynamic approach to sequentially execute the ILP on short transportation segments. Recommendations are made about how to define the size of the transportation segments, based on factors related to downstream traffic conditions to achieve a near global optimal solution. Freeman Hall, Clemson, SC, 29634, United States, Marlin Wolf Ulmer, Barrett Thomas, Stein W. Wallace

n SB08 North Bldg 124A Paths and Clusters in Networks Sponsored: Optimization/Network Optimization Sponsored Session

Chair: Foad Mahdavi Pajouh, University of Massachusetts, Boston, MA 1 - Finding the Longest Path in a Structurally Perturbed Directed Acyclic Graph Golshan Madraki, Assistant Professor, Clarkson University, 8 Clarkson Ave, Potsdam, NY, 13699, United States In a structurally perturbed Directed Acyclic Graph (DAG) multiple edges are added and deleted simultaneously. Finding the longest path in the perturbed DAGs after perturbation without doing the calculation from the scratch is a critical challenge. The solution for this problem can solve and improve different problems in manufacturing system, transportation, telecommunications and etc. All previous researched considered single edge addition/deletion at a time. However, this research proposes an efficient algorithm called SPA to handle multiple edge deletions/additions with a single pass. This solution is more efficient in terms of time complexity than the previous approaches. 2 - Exact IP-based Approaches for the Longest Induced Path Problem Dmytro Matsypura, University of Sydney, Sydney, Australia Graph diameter, which is defined as the longest shortest path in the graph, is often used to quantify graph communication properties. In particular, it pro- vides a very intuitive measure of the worst-case pairwise distance. However, in many practical settings where vertices can either fail or be overloaded, or destroyed by an adversary and thus, cannot be used in any communication or transportation path, it is natural to consider a more general measure of worst-case distance. One such measure is the longest induced path. The longest induced path problem is defined as the problem of finding a subgraph of largest cardinality such that this subgraph is a simple path. In contrast to the polyno- mially computable graph diameter, this problem is NP-hard. In this paper, we focus on exact solution approaches for the problem based on integer program- ming (IP) techniques. We first propose three conceptually different IP models and study their basic properties. To improve the performance of standard IP solvers, we propose an exact iterative algorithm, which solves a sequence of smaller IPs in order to obtain an optimal solution for the original problem. In addition, we develop a heuristic capable of finding induced paths in larger net- works. Finally, we conduct an extensive computational study to evaluate the performance of the proposed solution methods. 3 - Facility Location in Sparse Networks with Application to Aircraft Gate Assignment Airport gate assignment problem is a problem that involves assigning scheduled flights to airport gates during a specific time period. Due to the fact that air traffic has almost doubled during the past three decades, there is a need for assigning flights to gates in an efficient way. Existing mathematical formulation approaches are developed mostly based on either the Quadratic Assignment Problem (QAP) or they include quadratic terms which both approaches can only be used to solve small scale problems. In this research, a novel graph based formulation is developed to exploit the sparsity of such networks. The efficiency of the formulation is examined by running the model for some numerical example. 4 - Identifying Resilient Clusters in Networks with Randomly Changing Topology Maciej Rysz, University of Florida, 1751 Thomas St, Niceville, FL, 32578, United States We propose a two-stage stochastic programming framework for designing or identifying “resilientö, or “repairable clusters in graphs whose topology may undergo a stochastic transformation. The reparability of a cluster is defined in terms of a budget constraint, which limits the repairs that can be made to the cluster when restoring its original structural properties after observing random changes to the graph’s topology. A combinatorial branch-and-bound algorithm is developed, and its effectiveness is illustrated on the example of a two-stage stochastic maximum k-club problem. 5 - The Most Degree-central Clique Problem Haonan Zhong, University of Massachusetts, Boston, MA, United States, Foad Mahdavi Pajouh The most degree-central clique problem is to find a clique of maximum degree centrality in a graph. We addressed the computational complexity of this problem and proposed a series of theoretical foundations to build a combinatorial branch and bound algorithm for its solution. The performance of our proposed algorithm is tested on real life networks and random graphs. Mohammad Javad Naderi, Oklahoma State University, Stillwater, OK, 74075, United States, Austin Buchanan

33