Search

We introduce a compact formulation for the fixed-destination multi-depot asymmetric travelling salesman problem (FD-mATSP). It consists of m salesmen distributed among D depots who depart from and return to their respective origins after visiting a set of customers. The proposed model exploits the multi-depot aspect of the problem by labelling the arcs to identify the nodes that belong to the same tour. Our experimental investigation shows that the proposed-two index formulation is versatile and effective in modelling new variations of the FD-mATSP compared with existing formulations. We demonstrate this by applying it for the solution of two important extensions of the FD-mATSP that arise in logistics and manufacturing environments.

In this paper, we present a single-commodity flow-based formulation for the high-multiplicity asymmetric traveling salesman problem (HMATSP), which is an extension of the asymmetric traveling sales...

We address the robust weekly aircraft routing and retiming problem, which requires determining weekly schedules for a heterogeneous fleet that maximizes the aircraft on-time performance, minimizes the total delay, and minimizes the number of delayed passengers. The fleet is required to serve a set of flights having known departure time windows while satisfying maintenance constraints. All flights are subject to random delays that may propagate through the network. We propose to solve this problem using a hybrid optimization-simulation approach based on a novel mixed-integer nonlinear programming model for the robust weekly aircraft maintenance routing problem. For this model, we provide an equivalent mixed-integer linear programming formulation that can be solved using a commercial solver. Furthermore, we describe a Monte-Carlo-based procedure for sequentially adjusting the flight departure times. We perform an extensive computational study using instances obtained from a major international airline, having up to 3387 flights and 164 aircraft, which demonstrates the efficacy of the proposed approach. Using the simulation software SimAir to assess the robustness of the solutions produced by our approach in comparison with that for the original solutions implemented by the airline, we found that on-time performance was improved by 9.8-16.0%, cumulative delay was reduced by 25.4-33.1%, and the number of delayed passengers was reduced by 8.2-51.6%. 1 2017 Elsevier Ltd This research was made possible by NPRP Grant No. 06-818-5-094 from the Qatar National Research Fund (a member of The Qatar Foundation). The statements made herein are solely the responsibility of the authors. Scopus

We present an algorithm to solve single and multiple asymmetric traveling salesmen problems (ATSP and mATSP) by generating violated subtour elimination constraints from specific integer solutions. ...

Given a daily flight schedule and a set of aircraft fleets, the airline scheduling problem assigns individual aircraft and groups of crew to each flight based on specific considerations of aircraft maintenance requirements and crew work rules, respectively. Traditionally, this problem has been sequentially broken down into several stages, where the fleet assignment problem, which is solved first, partitions the entire flight network into subnetworks according to fleet types, followed by respectively solving the aircraft routing and crew pairing problems to generate suitable aircraft and crew rotations. However, this sequential approach ignores the interdependencies among the stages, leading to suboptimal, or even infeasible, solutions. In this paper, we propose an integrated model and solution approach that incorporates the fleet assignment (with itinerary-based demands), aircraft routing, and crew pairing problems within a single framework. We solve the resulting formulation of the problem by using a Benders decomposition approach, along with several acceleration strategies. Computational results obtained by using real-life data from a major U.S. airline demonstrate the benefits of the integrated approach. 2015 INFORMS. This research has been supported by the National Science Foundation [Grant CMMI-0969169] and also, this paper was made possible by the National Priority Research Program (NPRP) [Grant NPRP06-818-5-094] from the Qatar National Research Fund (a member of the Qatar Foundation). Scopus

The daily crew pairing problem (DCPP) seeks to generate a set of minimal-cost pairings that covers all the planned daily flights while complying with a variety of labor regulations, safety rules, and policies of the airline. The DCPP is a highly complex and large-scale optimization problem that is often modeled using a set-partitioning formulation and then solved via advanced optimization techniques (i.e., specialized column generation or branch-and-price algorithms). To complement this approach, we present a novel compact polynomial-sized nonlinear formulation for the DCPP, which is then linearized and lifted using the reformulation-linearization technique (RLT). Moreover, we propose two enhancement strategies to further improve the computational performance of the proposed formulation. The experimental results show that the compact formulation can be solved efficiently by commercial software without complicated algorithmic implementations, thus facilitating its use in the airline industry. Scopus

Cooperation has become an essential element in spectrum sharing between the primary and secondary networks. A new trend in cooperation is to allow the primary and secondary networks to cooperate on the node level for data forwarding. This new paradigm allows to pool network resources from both the primary and secondary networks and allows users in each network to access a much richer network infrastructure in a combined network. This paper offers an in-depth study of such node-level cooperation by explaining its optimal throughput curve—the maximum achievable throughput for both the primary and secondary users. We formulate the problem as a multicriteria optimization problem with the goal of maximizing the throughput of both the primary and secondary users. Through a novel approach based on weighted Chebyshev norm, we transform the multicriteria optimization problem into a single criteria optimization problem and find a sequence of Pareto-optimal points iteratively. Based on the Pareto-optimal points, we construct the throughput curve and show that it provides an $\varepsilon $ -approximation to the optimal curve. We prove some important properties of the optimal throughput curve. Through a case study, we show that the throughput region (the area under the throughput curve) under node-level cooperation is substantially larger than that when there is no node-level cooperation.

In recent years, many resource allocation models have been developed to protect critical infrastructure by maximizing system resiliency or minimizing its vulnerability to disasters or disruptions. However, these are often computationally intensive and require simplifying assumptions and approximations. In this study, we develop a robust and representative, yet tractable, model for optimizing maintenance planning of generic network-structured systems (transportation, water, power, communication). The proposed modeling framework examines models that consider both linear and nonlinear objective functions and enhances their structure through suitable manipulations. Moreover, the designed models inherently capture the network topography and the stochastic nature of disruptions and can be applied to network-structured systems where performance is assessed based on network flow efficiency and mobility. The developed models are applied to the Istanbul highway system in order to assess their relative compu...