Most of the existing path planning methods of automated guided vehicles (AGVs) are static. This paper proposes a new methodology for the path planning of a fleet of AGVs to improve the flexibility, robustness, and scalability of the AGV system. We mathematically describe the transport process as a dynamical system using an ad hoc mixed logical dynamical (MLD) model. Based on our MLD model, model predictive control is proposed to determine the collision paths dynamically, and the corresponding optimization problem is formulated as 0-1 integer linear programming. An alternating direction method of multipliers (ADMM)-based decomposition technique is then developed to coordinate the AGVs and reduce the computational burden, aiming for real-time decisions. The proposed methodology is tested on industrial scenarios, and results from numerical experiments show that the proposed method can obtain high transport productivity of the multi-AGV system at a low computational burden and deal with uncertainties resulting from the industrial environment.@en

This paper investigates a novel routing problem of a multi-robot station in a manufacturing cell. In the existing literature, the objective is to minimize the cycle time or energy consumption separately. The routing problem considered in this paper aims to reduce the cycle time and energy consumption jointly for each robot while avoiding collisions between these robots. For this routing problem, we propose a new flexible time-space network model that allows us to reduce energy consumption while minimizing the cycle time. The corresponding optimization problem is Mixed-Integer Nonlinear Programming (MINLP). For addressing its computational complexity, this paper designs a metaheuristic algorithm tailored to the studied problem and proposes an ϵ-constraint algorithm to study the trade-off between these two objectives. We conduct industrially relevant simulation experiments of case studies to show its effectiveness, in comparison to a conventional method, two state-of-the-art solvers, and two commonly-used metaheuristics. The results show that the proposed methodology can reduce energy consumption by up to 30% without compromising the cycle time. Meanwhile, the proposed algorithm can provide efficient solutions within a reasonable computation time. Note to Practitioners-This paper is motivated by the problem of improving energy efficiency when routing cooperative robots in a manufacturing station. In current approaches for routing multi-robot stations, the cycle time and energy consumption are minimized separately. This paper focuses on the movement of the robot end-effector and its connected joint and suggests a new approach to minimize these two objectives jointly by proposing a new mathematical model. The resulting planning problem is computationally intractable. A customized metaheuristic algorithm is thus designed for efficiently solving this planning problem. Our meta-heuristic algorithm is integrated with the ϵ-constraint method to study the relationship between these two objectives. Simulation experiments suggest that this approach can reduce energy consumption considerably, for the shortest cycle time, compared with the current approaches. In future research, the movements of multi-joints will be investigated whereby 3-D collision-free trajectory planning will be considered.@en

Reducing pollutant emissions and promoting sustainable mobility solutions, including Public Transport (PT), are increasingly becoming key objectives for policymakers worldwide. In this work we develop an optimal vehicle scheduling approach for next generation PT systems, considering the instance of mixed electric / hybrid fleet. Our objective is that of investigating to what extent electrification, coupled with optimal fleet management, can yield operational cost savings for PT operators. We propose a Mixed Integer Linear Program (MILP) to address the problem of optimal scheduling of a mixed fleet of electric and hybrid / non-electric buses, coupled with an ad-hoc decomposition scheme aimed at enhancing the scalability of the proposed MILP. Two case studies arising from the PT network of the city of Luxembourg are employed in order to validate the model; sensitivity analysis to fleet design parameters is performed, specifically in terms of fleet size and fleet composition. Conclusions point to the fact that careful modelling and handling of mixed-fleet conditions are necessary to achieve operational savings, and that marginal savings gradually reduce as more conventional buses are replaced by their electric counterparts. We believe the methodology proposed may be a key part of advanced decision support systems for policymakers and operators that are dealing with the on-going transition from conventional bus fleets towards greener transport solutions.@en

In this paper, a new time-space network model is proposed for addressing the time-dependent rural postman problem (TDRPP) of a single vehicle. The proposed model follows the idea of arc-path alternation to form a feasible and complete route. Based on the proposed model, the time dependency of the TDRPP is better described to capture its dynamic process, compared to the existing methods using a piecewise constant function with limited intervals. Furthermore, the property of first-in-first-out (FIFO) can be satisfied with the time spent on each arc. We investigate the FIFO property for the considered time-dependent network and key optimality property for the TDRPP. Based on this property, a dedicated genetic algorithm (GA) is proposed to efficiently solve the considered TDRPP that suffers from computational intractability for large-scale cases. Comprehensive simulation experiments are conducted for various time-dependent networks to show the effectiveness of the proposed GA.@en

In this paper, a new time-space network model is proposed for addressing the time-dependent rural postman problem (TDRPP) of a single vehicle. The proposed model follows the idea of arc-path alternation to form a feasible and complete route. Based on the proposed model, the time dependency of the TDRPP is better described to capture its dynamic process, compared to the existing methods using a piecewise constant function with limited intervals. Furthermore, the property of first-in-first-out (FIFO) can be satisfied with the time spent on each arc. We investigate the FIFO property for the considered time-dependent network and key optimality property for the TDRPP. Based on this property, a dedicated genetic algorithm (GA) is proposed to efficiently solve the considered TDRPP that suffers from computational intractability for large-scale cases. Comprehensive simulation experiments are conducted for various time-dependent networks to show the effectiveness of the proposed GA.@en

Optimization models for railway traffic rescheduling in the last decade tend to develop along two main streams. On the one hand, train scheduling models strive to incorporate any relevant detail of the railway infrastructure having an impact on the feasibility and quality of the solutions from the viewpoint of infrastructure managers. On the other hand, delay management models focus on the impact of rescheduling decisions on the quality of service perceived by the passengers, and in the interest of the train operating company. Models in the first stream are mainly microscopic, while models in the second stream are mainly macroscopic. This paper aims at merging these two streams of research by developing microscopic delay management approaches. A variety of solution algorithms are proposed, that compute a solution to the studied problem; the obtained solutions correspond to Nash equilibria of the strategic interaction of the players (train operating company and infrastructure manager). Computational results based on a real-world Dutch railway network quantify the trade-off between the minimization of train delays and passenger travel times, and show that good compromise solutions can be found within a limited computation time.@en

Optimization models for railway traffic rescheduling in the last decade tend to develop along two main streams. On the one hand, train scheduling models strive to incorporate any relevant detail of the railway infrastructure having an impact on the feasibility and quality of the solutions from the viewpoint of infrastructure managers. On the other hand, delay management models focus on the impact of rescheduling decisions on the quality of service perceived by the passengers, and in the interest of the train operating company. Models in the first stream are mainly microscopic, while models in the second stream are mainly macroscopic. This paper aims at merging these two streams of research by developing microscopic delay management approaches. A variety of solution algorithms are proposed, that compute a solution to the studied problem; the obtained solutions correspond to Nash equilibria of the strategic interaction of the players (train operating company and infrastructure manager). Computational results based on a real-world Dutch railway network quantify the trade-off between the minimization of train delays and passenger travel times, and show that good compromise solutions can be found within a limited computation time.@en

Reducing pollutant emissions and promoting sustainable mobility solutions, including Public Transport, are increasingly becoming key objectives for policymakers worldwide. In order to jointly achieve these goals, careful consideration should be put on the operational cost and management of PT services, in order to promote the adoption of green mobility solutions and advanced management techniques by operators. In this work we develop a dynamic fleet management approach for next generation Public Transportation systems, considering the instance of mixed electric / hybrid fleet. Our objective is that of investigating to what extent electrification, coupled with optimal fleet management, can yield operational cost savings for PT operators, explicitly considering real-Time disturbances, including delays, service disruptions etc. We propose a Mixed Integer Linear Program to address the problem of optimal scheduling of a mixed fleet of electric and hybrid / non-electric buses, and employ it as predictor in a Model Predictive Control approach. Test results based upon a real-life scenario showcase how the proposed approach is indeed capable of yielding a sizable reduction in operational costs, even when considerable disturbances arise from the underlying system.@en

Reducing pollutant emissions and promoting sustainable mobility solutions, including Public Transport, are increasingly becoming key objectives for policymakers worldwide. In order to jointly achieve these goals, careful consideration should be put on the operational cost and management of PT services, in order to promote the adoption of green mobility solutions and advanced management techniques by operators. In this work we develop a dynamic fleet management approach for next generation Public Transportation systems, considering the instance of mixed electric / hybrid fleet. Our objective is that of investigating to what extent electrification, coupled with optimal fleet management, can yield operational cost savings for PT operators, explicitly considering real-Time disturbances, including delays, service disruptions etc. We propose a Mixed Integer Linear Program to address the problem of optimal scheduling of a mixed fleet of electric and hybrid / non-electric buses, and employ it as predictor in a Model Predictive Control approach. Test results based upon a real-life scenario showcase how the proposed approach is indeed capable of yielding a sizable reduction in operational costs, even when considerable disturbances arise from the underlying system.@en

Operations of Automated Guided Vehicles (AGVs) are desired to be more energy-efficient while maintaining high transport productivity, motivated by the green production requirements. This paper investigates a new energy-efficient planning problem for determining conflict-free paths of the AGVs in its transport roadmap. In this problem, the vehicle path and transport time in the roadmap are jointly optimized, based on a flexible time–space network (FTSN). We provide the mathematical problem formulation of the energy-efficient path planning problem. The resulting optimization problem is proved to be a non-convex mixed-integer nonlinear programming which is computationally intractable. We further propose a hybrid metaheuristic that integrates the genetic algorithm and estimation of the distribution algorithm to improve its computational efficiency. Numerical results show the effectiveness of the developed algorithm based on the FTSN framework, compared to the existing metaheuristics, the conventional path planning method, and a commercial solver. The proposed method has a wide application in improving energy use of material handling, providing a guiding significance on promoting cleaner production of flexible manufacturing systems.@en

This paper addresses the real-time problem of coordinating aircraft ground and air operations in an airport area. At a congested airport, airborne decisions are related to take-off and landing operations, while ground (taxiway) decisions consist of scheduling aircraft movements between the gates and the runways. Since the runways are the initial/terminal points of both decisions, coordinated actions have a great potential to improve the overall performance. However, in the traffic control practice the different decisions are taken by different controllers, at least in large airports. Weak coordination may result in long queues at the runways, with increasing aircraft delays and energy consumption. This paper investigates models, methods and policies for improving the coordination between taxiway scheduling and airborne scheduling. The performance of a solution is measured in terms of delay and travel time, the latter being related to the energy consumption of an aircraft. A microscopic mathematical formulation is adopted to achieve reliable solutions. Exact and heuristic methods have been analysed in combination with the different policies, based on practical-size instances from Amsterdam Schiphol airport, in the Netherlands. Computational experience shows that good quality solutions can be found within limited time, compatible with real-time operations.@en

Intelligent decision support systems for the real-time management of landing and take-off operations can be very effective in helping air traffic controllers to limit airport congestion at busy terminal control areas. The key optimization problem to be solved regards the assignment of airport resources to take-off and landing aircraft and the aircraft sequencing on them. The problem can be formulated as a mixed integer linear program. However, since this problem is strongly NP-hard, heuristic algorithms are typically adopted in practice to compute good quality solutions in a short computation time. This paper presents a number of algorithmic improvements implemented in the AGLIBRARY solver (a state-of-the-art optimization solver to deal with complex routing and scheduling problems) in order to improve the possibility of finding good quality solutions quickly. The proposed framework starts from a good initial solution for the aircraft scheduling problem with fixed routes (given the resources to be traversed by each aircraft), computed via a truncated branch-and-bound algorithm. A metaheuristic is then applied to improve the solution by re-routing some aircraft in the terminal control area. New metaheuristics, based on variable neighbourhood search, tabu search and hybrid schemes, are introduced. Computational experiments are performed on an Italian terminal control area under various types of disturbances, including multiple aircraft delays and a temporarily disrupted runway. The metaheuristics achieve solutions of remarkable quality, within a small computation time, compared with a commercial solver and with the previous versions of AGLIBRARY.@en

Optimization models for railway traffic rescheduling tackle the problem of determining, in real-time, control actions to reducing the effect of disturbances in railway systems. In this field, mainly two research streams can be identified. On the one hand, train scheduling models are designed to include all conditions relevant to feasible and efficient operation of rail services, from the viewpoint of operations managers. On the other hand, delay management models focus on the impact of rescheduling decisions on the quality of service perceived by the passengers. Models in the first stream are mainly microscopic, while models in the second stream are mainly macroscopic. This paper aims at merging these two streams of research by developing microscopic passenger-centric models, solution algorithms and lower bounds. Several fast heuristic methods are proposed, based on alternative decompositions of the model. A lower bound is proposed, consisting of the resolution of a set of min-cost flow problems with activation constraints. Computational experiments, based on multiple test cases of the real-world Dutch railway network, show that good quality solutions and lower bounds can be found within a limited computation time.@en

Optimization models for railway traffic rescheduling tackle the problem of determining, in real-time, control actions to reducing the effect of disturbances in railway systems. In this field, mainly two research streams can be identified. On the one hand, train scheduling models are designed to include all conditions relevant to feasible and efficient operation of rail services, from the viewpoint of operations managers. On the other hand, delay management models focus on the impact of rescheduling decisions on the quality of service perceived by the passengers. Models in the first stream are mainly microscopic, while models in the second stream are mainly macroscopic. This paper aims at merging these two streams of research by developing microscopic passenger-centric models, solution algorithms and lower bounds. Several fast heuristic methods are proposed, based on alternative decompositions of the model. A lower bound is proposed, consisting of the resolution of a set of min-cost flow problems with activation constraints. Computational experiments, based on multiple test cases of the real-world Dutch railway network, show that good quality solutions and lower bounds can be found within a limited computation time.@en

We consider the problem of optimally determining the sequence of electric and hybrid buses departing from a multi-line bus terminal, considering both service constraints (schedule adherence) and energy constraints (electric bus charging status, bus recharging scheduling in capacitated facilities). The problem is formulated as a Mixed Integer Linear Program, with the objective of minimizing the total operational cost for the bus lines in question. System dynamics are captured by practical sets of constraints, ranging from scheduling adherence to discharge-recharge dynamics. Individual operational costs at the bus level and at the trip level are fully parametrized, allowing for extensive sensitivity analysis. We investigate a real-life case study based on the city of Luxembourg, where two charging stations have been installed in the central station's bus terminal. Experimental results show that, while full electrification is indeed possible, the required fleet size depends strongly on the given line(s) timetable.@en

We consider the problem of optimally determining the sequence of electric and hybrid buses departing from a multi-line bus terminal, considering both service constraints (schedule adherence) and energy constraints (electric bus charging status, bus recharging scheduling in capacitated facilities). The problem is formulated as a Mixed Integer Linear Program, with the objective of minimizing the total operational cost for the bus lines in question. System dynamics are captured by practical sets of constraints, ranging from scheduling adherence to discharge-recharge dynamics. Individual operational costs at the bus level and at the trip level are fully parametrized, allowing for extensive sensitivity analysis. We investigate a real-life case study based on the city of Luxembourg, where two charging stations have been installed in the central station's bus terminal. Experimental results show that, while full electrification is indeed possible, the required fleet size depends strongly on the given line(s) timetable.@en

Public transport services are currently executing or planning a fundamental transition from traditional buses to electric buses. During this transition phase, the public transport offering is fulfilled with a mixed fleet across multiple bus terminals, which poses operational challenges for optimal vehicle scheduling, a problem not yet addressed in literature. As researchers in Transport Engineering and Operational Research at the University of Luxembourg, in collaboration with the Roma Tre University, we support the Ministry of Transport of Luxembourg and Volvo buses by modelling and simulating this transition phase, to help them managing and solving such challenges. In this work we develop a mixed-integer linear programming (MILP) formulation of the problem and implement a time-based decomposition framework, through which we can optimize real-life daily instances. This method is tested on the main urban bus lines that connect Central Station, Luxembourg Airport and ten other major terminals within Luxembourg City, providing (near) optimal solutions that explicitly consider the energy constraints arising from electric bus operations, while establishing an advantageous trade-off between delaying trips, to implement quick-charging of electric buses, and performing the same trip with costlier traditional buses. The results show a consistent decrease of operational costs as the percentage of e-buses in the fleet increases.@en

Optimization models for railway traffic rescheduling in the last decade tend to develop along two main streams. One the one hand, train scheduling models strives to incorporate any relevant detail of the railway infrastructure having an impact on the feasibility and quality of the solutions from the viewpoint of operations managers. On the other hand, delay management models focus on the impact of rescheduling decisions on the quality of service perceived by the passengers. Models in the first stream are mainly microscopic, while models in the second stream are mainly macroscopic. This paper aims at merging these two streams of research by developing microscopic passenger-centric models, solution algorithms and lower bounds. Fast iterative algorithms are proposed, based on a decomposition of the problem and on the exact resolution of the subproblems. A new lower bound is proposed, consisting of the resolution of a set of min-cost flow problems with activation constraints. Computational experiments, based on a real-world Dutch railway network, show that good quality solutions and lower bounds can be found within a limited computation time.@en

This work addresses a tactical railway traffic management problem focused on the opti-mization of train dispatching decisions and timing decisions related to short-term main-tenance works in a railway network subject to disturbed process times. This is modeled as a mixed-integer programming formulation in which the traffic flow and track mainten-ance variables, constraints and objectives are integrated under a stochastic environment. The resulting bi-objective optimization problem is to minimize the deviation from a sche-duled plan and to maximize the number of aggregated maintenance works. The two ob-jectives require to schedule competitive train operations versus maintenance works on the same infrastructure elements. Numerical experiments are performed on a realistic railway network. We measure the quality of the integrated solutions in terms of their robustness to random perturbations of the train travel times and of the maintenance works. Pareto op-timal methods are compared for the bi-objective problem. We also evaluate the impact of introducing routing stability constraints in order to force the trains to keep the same route among the different stochastic disturbed scenarios. The experiments show that forcing the routing stability reduces the routing flexibility and the ability to optimize the two perfor-mance indicators when dealing with stochastic disturbances of process times.@en