Abstract

Logistic Service Providers (LSPs) offering hinterland transportation face the trade-off between efficiently using the capacity of long-haul vehicles and minimizing the first and last-mile costs. To achieve the optimal trade-off, freights have to be consolidated considering the variation in the arrival of freight and their characteristics, the applicable transportation restrictions, and the interdependence of decisions over time. We propose the use of a Markov model and an Approximate Dynamic Programming (ADP) algorithm to consolidate the right freights in such transportation settings. Our model incorporates probabilistic knowledge of the arrival of freights and their characteristics, as well as generic definitions of transportation restrictions and costs. Using small test instances, we show that our ADP solution provides accurate approximations to the optimal solution of the Markov model. Using larger problem instances, we show that our modeling approach has significant benefits when compared to common-practice heuristic approaches. Document type: Part of book or chapter of book

Abstract

In this paper we explore tramp ship routing and scheduling. Tramp ships operate much like taxies following the available demand. Tramp operators can determine some of their demand in advance by entering into long-term contracts and then try to maximise profits from optional voyages found in the spot market. Routing and scheduling a tramp fleet to best utilise fleet capacity according to current demand is therefore an ongoing and complicated problem. Here we add further complexity to the routing and scheduling problem by incorporating voyage separation requirements that enforce a minimum time spread between some voyages. The incorporation of these separation requirements helps balance the conflicting objectives of maximising profit for the tramp operator and minimising inventory costs for the charterer, since these"br/"costs increase if similar voyages are not performed with some separation in time. We have developed a new and exact branch-and-price procedure for this problem. We use a dynamic programming algorithm to generate columns and describe a time window branching scheme used to enforce the voyage separation requirements which we relax in the master problem. Computational results show that our algorithm in general finds optimal solutions very quickly and performs much faster compared to an earlier a priori path generation method. Finally, we compare our method to an earlier adaptive large neighbourhood search heuristic and find that on similar-sized instances our approach generally uses less time to find the optimal solution than the adaptive large neighbourhood search method uses to find a heuristic solution. Document type: Book

Abstract

Traditional solutions to shortest path problems on time-varying transportation networks use traffic information only at precise moments regardless of considering the fact that the travel time through any link is dependent on the time entering that link. In this study, travel speed rather than travel time on each link is used as the time period dependent parameter to model time-dependent transportation networks, and a First-In-First-Out (FIFO) condition satisfied computational function of link travel time is then deduced based on kinematics. Finally, a temporally adaptive A* shortest path algorithm on this FIFO network is presented, where the time factor is introduced into the evaluation function, and the Euclidean distance divided by the maximum possible travel speed is used as a heuristic evaluator. An experiment on a real road network shows that the proposed algorithm is capable of foreseeing and bypassing forthcoming traffic congestion, at a cost only about 10% more in computational time than the traditional algorithm. In addition, frequent path reoptimization required with use of the traditional algorithm is effectively avoided. Document type: Part of book or chapter of book

Abstract

We consider a stochastic routing model in which the goal is to find the optimal route that incorporates a measure of risk The problem arises in traffic engineering, transportation and even more abstract settings such as task planning (where the time to execute tasks is uncertain), etc The stochasticity is specified in terms of arbitrary edge length distributions with given mean and variance values in a graph The objective function is a positive linear combination of the mean and standard deviation of the route Both the nonconvex objective and exponentially sized feasible set of available routes present a challenging optimization problem for which no efficient algorithms are known In this paper we evaluate the practical performance of algorithms and heuristic approaches which show very promising results in terms of both running time and solution accuracy. Document type: Part of book or chapter of book

Abstract

Our research deals with the problem of the charging scheduling of electric vehicles (EV). The variation in the total power available to load vehicles, user the behaviour constraints and the uncertainties of daily energy demands require an efficient and secure scheduling. We defined five industrial configurations: ACPF (1,2) and ACPV (1a, 1b and 2), each of which corresponds to a set of technical constraints. Studies on formulations, including a conjunctive and a disjunctive, are based on the analysis of the strength of their LP-relaxation. The matrix form of the mathematical formula is composed of a partitioned matrix, which is decomposable by the Dantzig-Wolfe principles. The latter allows us to develop a Branch-and-Price Algorithm for the exact solution of the problem. A deterministic constructive heuristic was then designed for the allocation of the resource, which is very efficient: a quick resolution (less than a second) for a car park with about thirty EVs. Finally, to implement all algorithms in the microprocessor, and to establish a forecasting model and an online scheduling, we have created a stand-alone scheduler, based on the predictive-reactive rescheduling. The research carried out is part of the problems of energy reasoning. They, therefore, can combine with other works, including the smart grid problems; Notre travail de recherche traite de la problématique de l’ordonnancement de recharge des véhicules électriques (VE). La variation de la puissance totale disponible pour charger des véhicules, les contraintes de comportement des utilisateurs et l'incertitude des demandes énergétiques journalières demandent un ordonnancement efficace et sécurisé. Nous avons défini cinq configurations industrielles : ACPF (1,2) et ACPV (1a, 1b et 2) qui correspondent chacune à un ensemble de contraintes techniques. Les études sur les formulations, dont une conjonctive et une disjonctive, reposent sur l’analyse de la force de leurs relaxation-LP. La forme matricielle de la formule mathématique est composée d’une matrice partitionnée, qui est décomposable par le principe de Dantzig-Wolfe. Cette dernière nous permets de développer un algorithme de type Branch-and-Price pour la résolution exacte du problème. Une heuristique constructive déterministe a ensuite été conçue pour l’allocation de la ressource, qui se trouve très efficace : une résolution rapide (moins d’une seconde) pour un parking d’une trentaine VEs. Finalement, pour implémenter tous les algorithmes dans le microprocesseur, et pour établir un modèle prévisionnel et un ordonnancement en temps réel, nous avons créé un planificateur autonome, qui se base sur le réordonnancement prédictif-réactif. Les recherches effectuées font partie des problèmes de raisonnement énergétique. Elles possèdent donc la capacité de se combiner avec d’autres travaux, notamment le problème de smart grid

Abstract

International audience; The present paper proposes a novel method for computing inter-domain paths subject to multiple independent additive constraints in MPLS-TE networks. An efficient solution to this problem is a key element for providing services with guaranteed performance across domain boundaries. However, the inherent hardness of the multi-constrained path computation as well as inter-domain scalability and security constraints complicate the computation problem. We propose a novel algorithm named kID-MCP that tackles the computational complexity of the problem by reducing the number of paths included in the computation process. kID-MCP is compatible with existing techniques and fulfills the security requirements. We undergo a complexity analysis that shows that kID-MCP scales well. Moreover, a simulation study reveals that kID-MCP finds a solution in most situations. These results indicate that the computation of inter-domain multi-constrained paths is tractable in practice, which opens interesting perspectives for QoS routing and traffic engineering among multiple operators.

Abstract

Detecting and solving aircraft conflicts, which occur when aircraft sharing the same airspace are too close to each other according to their predicted trajectories, is a crucial problem in Air Traffic Management. We focus on mixed-integer optimization models based on speed regulation. We first solve the problem to global optimality by means of an exact solver. The problem being very difficult to solve, we also propose a heuristic procedure where the problem is decomposed and it is locally solved by an exact solver. Computational results show that the proposed approach provides satisfactory results in reasonable time.