1,720,994 research outputs found
Preface of the volume for the 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)
No full textThe 19th ATMOS symposium (ATMOS’19) was held in connection with ALGO’19and hosted by Technische Universität München in Munich, Germany, on September 12-13,2019. Topics of interest were all optimization problems for passenger and freight transport,including, but not limited to, demand forecasting, models for user behavior, design of pricing systems, infrastructure planning, multi-modal transport optimization, mobile applications for transport, congestion modelling and reduction, line planning, timetable generation, routing and platform assignment, vehicle scheduling, route planning, crew and duty scheduling,rostering, delay management, routing in road networks, and traffic guidance
Robust optimization models for integrated train stop planning and timetabling with passenger demand uncertainty
Full text linkIn this work, we consider the problem of scheduling a set of trains (i.e., determining their departure and arrival times at the visited stations) and simultaneously deciding their stopping patterns (i.e., determining at which stations the trains should stop) with constraints on passenger demand, given as the number of passengers that travel between an origin station and a destination station. In particular, we face the setting in which demand can be uncertain, and propose Mixed Integer Linear Programming (MILP) models to derive robust solutions in planning, i.e., several months before operations. These models are based on the technique of Light Robustness, in which uncertainty is handled by inserting a desired protection level, and solution efficiency is guaranteed by limiting the worsening of the nominal objective value (i.e., the objective value of the problem in which uncertainty is neglected). In our case, the protection is against a potential increased passenger demand, and the solution efficiency is obtained by limiting the train travel time and the number of train stops. The goal is to determine robust solutions in planning so as to reduce the passenger inconvenience that may occur in real-time due to additional passenger demand. The proposed models differ in the way of inserting the protection, and show different levels of detail on the required information about passenger demand. They are tested on real-life data of the Wuhan–Guangzhou high-speed railway line under different demand scenarios, and the obtained results are compared with those found by solving the nominal problem. The comparison shows that robust solutions can handle uncertain passenger demand in a considerably more effective way
Robustness in train timetabling
No full textWe propose a Lagrangian-based heuristic approach to obtain robust solutions to the Train Timetabling Problem (TTP) on a corridor (i.e. a single one-way line connecting two major stations). Roughly speaking, we define a solution to be robust if it allows to avoid delay propagation as much as possible. In particular, in the planning phase that we are considering the aim is to build timetables characterized by buffer times that can be used to absorb possible delays occurring at an operational level. In the TTP, we are given a set of stations S along the corridor, a set of trains T, and for each train an ideal timetable (i.e. the timetable suggested by the Train Operator). In the nominal TTP the aim is to change the ideal timetables for the trains as little as possible, while satisfying the track capacity constraints consisting of: - departure constraints (imposing a minimum headway between two consecutive departures from a station); - arrival constraints (imposing a minimum headway between two consecutive arrivals at a station); - overtaking constraints (avoiding overtaking between consecutive stations, since we are considering a single one-way line)
Models and algorithms for the Traveling Salesman Problem with Time-dependent Service times
Full text linkThe Traveling Salesman Problem with Time-dependent Service times (TSP-TS) is a generalization of the Asymmetric TSP, in which the service time at each customer is given by a (linear or quadratic) function of the corresponding start time of service. TSP-TS calls for determining a Hamiltonian tour (i.e. a tour visiting each customer exactly once) that minimizes the total tour duration, given by the sum of travel and service times. We propose a new Mixed Integer Programming model for TSP-TS, that is enhanced by lower and upper bounds that improve previous bounds from the literature, and by incorporating exponentially many subtour elimination constraints, that are separated in a dynamic way. In addition, we develop a multi-operator genetic algorithm and two Branch-and-Cut methods, based on the proposed model. The algorithms are tested on benchmark symmetric instances from the literature, and compared with an existing approach. The computational results show that the proposed exact methods are able to prove the optimality of the solutions found for a larger set of instances in shorter computing times. We also tested the Branch-and-Cut algorithms on larger size symmetric instances with up to 58 nodes and on asymmetric instances with up to 45 nodes, demonstrating the effectiveness of the proposed algorithms. In addition, we tested the genetic algorithm on symmetric and asymmetric instances with up to 200 nodes
Metaheuristic Algorithms for UAV Trajectory Optimization in Mobile Networks
No full textWe consider a mobile network in which traditional static terrestrial base stations are not capable of completely serving the existing user demand, due to the huge number of connected devices. In this setting, an equipped Unmanned Aerial Vehicle (UAV) can be employed to provide network connection where needed in a flexible way, thereby acting as an unmanned aerial base station. The goal is to determine the best UAV trajectory in order to serve as many users as possible. The UAV can move at different speeds and can serve users within its communication range, although the data rate depends on the positions of UAV and users. In addition, each user has a demand (e.g., the number of bits the user wants to download/upload from/to the network) and a time window during which requires the service. We propose a Biased Random-Key Genetic Algorithm (BRKGA) and a Simulated Annealing Algorithm (SAA), and compare them on realistic instances with more than 500 users in different settings
Knapsack problems — An overview of recent advances. Part I: Single knapsack problems
No full textAfter the seminal books by Martello and Toth (1990) and Kellerer, Pferschy, and Pisinger (2004), knapsack problems became a classical and rich research area in combinatorial optimization. The purpose of this survey, which is structured in two parts, is to cover the developments that appeared in this field after the publication of the latter volume. Part I is devoted to problems whose goal is to optimally assign items to a single knapsack. Besides the classical knapsack problems (binary, subset sum, bounded, unbounded, change-making), we review problems with special constraints (setups, multiple-choice, conflicts, precedences, sharing, compartments) as well as relatively recent fields of investigation, like robust and bilevel problems. The subsequent Part II covers multiple, multidimensional, and quadratic knapsack problems, and includes a succinct treatment of online and multiobjective knapsack problems
Optimization over time of reliable 5G-RAN with network function migrations
Full text linkResource optimization in 5G Radio Access Networks (5G-RAN) has to face the dynamics over time in networks with increasing numbers of nodes and virtual network functions. In this context, multiple objectives need to be jointly optimized, and key application requirements such as latency must be enforced. In addition, virtual network functions realizing baseband processing are subject to failures of the cloud infrastructure, requiring an additional level of reliability. Overall, this is a complex problem to solve, requiring fast algorithms to cope with dynamic networks while avoiding resource overprovisioning. This paper considers the problem of optimal virtual function placement in 5G-RAN with reliability against a single DU Hotel failure and proposes a solution that takes service dynamics into account. Firstly, the joint optimization of the total number of DU Hotels, of the RU-DU latency and of the backup DU sharing in a static traffic scenario is considered, and the DUOpt algorithm, based on Lexicographic Optimization, is proposed for solving efficiently this multiobjective problem. DUOpt splits the multi-objective problem into smaller Integer Linear Programming (ILP) subproblems that are sequentially solved, adopting for each one the most effective methodology to reduce the total execution time. The proposed DUOpt algorithm is extensively benchmarked to show its effectiveness in optimization of medium to large size networks: in particular, it is shown to greatly outperform an aggregate multi-objective approach, being able to compute optimal or close to optimal solutions for networks of several tens of nodes in computing times of a few seconds. Then, the problem is extended to a dynamic traffic scenario in which optimization is performed over time. In this context, in addition to the aforementioned objectives, the total number of network function migrations induced by multiple reoptimizations must be kept to the minimum. For solving efficiently this problem the DUMig algorithm is proposed, which extends and improves DUOpt. Reoptimization over a time horizon of one day in an illustrative dynamic traffic scenario is performed to evaluate the proposed DUMig algorithm against DUOpt, the latter being oblivious of the traffic dynamics. DUMig shows remarkable savings in the total number of migrations (above 86.1% for primary virtual functions and 83% for backup virtual functions) compared to DUOpt, while preserving near-optimal resource assignment
Knapsack problems — An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems
Full text linkAfter the seminal books by Martello and Toth (1990) and Kellerer, Pferschy, and Pisinger (2004), knapsack problems became a classical and rich research area in combinatorial optimization. The purpose of this survey, structured in two parts, is to cover the developments appeared in this field after the publication of the latter volume. Part I treats the classical single knapsack problems and their variants. The present Part II covers multiple, multidimensional, and quadratic knapsack problems, as well as other relevant variants, such as, e.g., multiobjective and online versions
Unmanned aerial base stations for NB-IoT: Trajectory design and performance analysis
No full textIn this paper, we consider a NarrowBand-Internet of Things (NB-IoT) network where an Unmanned Aerial Vehicle (UAV) is employed to gather data from IoT devices deployed in a given area. It is well known that UAVs may fly over the terrestrial plane, where and when needed, acting as Unmanned Aerial Base Stations (UABs). In order to serve as many ground IoT devices as possible, a proper trajectory design is fundamental. As we show in the paper, the optimization of the UAV speed and the radio parameters are also essential. Specifically, this paper studies a cluster-based scenario, where IoT devices are deployed according to a Thomas process, and applies a Traveling Salesman Problem approach to design the UAB trajectory. Notably, our model considers the protocol constraints on the number of resource units available on the UAB's NPUSCH, and the data rate that it can provide to IoT devices. Our results reveal the impact of different design parameters, such as UAB speed and NPRACH periodicity on the network throughput and the number of requests served
A new lower bound for curriculum-based course timetabling
No full textIn this paper, we propose a new method to compute lower bounds for curriculum-based course timetabling (CTT), which calls for the best weekly assignment of university course lectures to rooms and time slots. The lower bound is obtained by splitting the objective function into two parts, considering one separate problem for each part of the objective function, and summing up the corresponding optimal values (or, in some cases, lower bounds on these values), found by formulating the two parts as Integer Linear Programs (ILPs). The solution of one ILP is obtained by using a column generation procedure. Experimental results show that the proposed lower bound is often better than the ones found by the previous methods in the literature, and also much better than those found by other new ILP formulations illustrated in this paper. The proposed approach is able to obtain improved lower bounds on real-world benchmark instances from the literature, used in the international timetabling competitions ITC2002 and ITC2007, proving for the first time that some of the best-known heuristic solutions are indeed optimal (or close to the optimal ones). © 2013 Elsevier Ltd
- …
