ABSTRACT We investigate a prospective Ride‐Sharing Mobility‐on‐Demand system designed to replace a significant portion of private car usage in European cities within a few years with affordable services operated by Shared Autonomous Electric Vehicles. A key feature of such a system is its ability to handle a very large number of transportation requests. We address both vehicle routing and energy management from a strategic perspective. Our goals are to estimate the fleet size, design prototype routes, and manage energy costs, while accounting for statistical demand patterns, various charging modes, and time‐dependent electricity prices. To achieve this, we introduce a decomposition scheme, DECO, which separates routing from recharge scheduling but allows their interaction via an aggregated fleet activity profile. This approach helps maintain energy feasibility under daily demand variations. We conduct numerical experiments on the urban network of Clermont–Ferrand, France, using 1400 designated pickup and drop‐off nodes. The simulated system serves up to 300 000 passenger requests with 10‐seat SAEVs having a range of 200 km. Results show that over 1700 vehicles are needed to serve all requests while accounting for energy constraints, under an average occupancy of around five passengers during peak hours. Analysis of charging behavior highlights off‐peak recharging preferences and cost‐sensitive mode selection. We further validate our heuristic DECO by comparing it with a baseline heuristic and with exact Mixed Integer Linear Program (MILP) solutions on small instances, demonstrating its ability to produce high‐quality results.

Photovoltaic platforms enable a single agent to simultaneously act as both a producer and a consumer of power, facilitating self-consumption strategies.This trend aligns with the goal of reducing CO2 emissions and is poised to significantly transform the structure of energy markets.It also introduces specific challenges-both tactical (e.g., pricing) and operational (e.g., routing, scheduling)-related to synchronizing energy production with consumption.In this work, we address the problem of efficiently routing a fleet of electric autonomous vehicles (EAVs), using energy that is either produced by a photovoltaic platform or purchased from the general power grid.We propose an exact Mixed-Integer Linear Programming (MILP) formulation of the problem, along with a heuristic approach that approximates the power production component of the model using surrogate representations.

International audience

We introduce a variant of the cumulative scheduling problem (CuSP) characterized by continuous modes, time windows, and a criterion that involves safety margin maximization. The study of this variant is motivated by the Geospatial based Environment for Optimisation Systems Addressing Fire Emergencies Horizon 2020 Project, which is devoted to the design of evacuation plans in the face of natural disasters and more specifically, wildfire. People and goods have to be transferred from endangered places to safe places, and evacuation planning consists of scheduling evacuee moves along precomputed paths under arc capacities and deadlines. The resulting model is relevant in other contexts, such as project or industrial process scheduling. We consider here several formulations of the continuous time-resource trade-off scheduling problem (CTRTP-TW) with a safety maximization objective. We establish a complete complexity characterization distinguishing polynomial and NP-hard special cases depending on key parameters. We show that the problem with fixed sequencing (i.e., with predetermined overlap or precedence relations between activities) is convex. We then show that the preemptive variant is polynomial, and we propose lower and upper bounds based on this relaxation. A flow-based mixed-integer linear programming formulation is presented, from which a branch-and-cut exact method and an insertion heuristic are derived. An exact dedicated branch-and-bound algorithm is also designed. Extensive computational experiments are carried out to compare the different approaches on evacuation planning instances and on general CTRTP-TW instances. The experiments also show the interest of the continuous model compared with a previously proposed discrete approximation. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This work was funded by the Horizon 2020 Marie Skłodowska-Curie Research and Innovation Staff Exchange European Project 691161 GEO-SAFE (Geospatial based Environment for Optimisation Systems Addressing Fire Emergencie). This work has also been supported by ANITI, the Artificial and Natural Intelligence Toulouse Institute. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0142 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0142 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

We study here the problem of scheduling unit-time jobs with release and due dates on identical machines while meeting a non-idling constraint and minimizing the number of active machines. Though this problem is theoretically solvable in polynomial time, designing an efficient algorithm remains an issue. We establish here several theoretical results that allow us to break symmetries and significantly reduce the search space, before designing and testing a very efficient$\boldsymbol{A}^{\ast }$like algorithm involving constraint propagation, which outperforms standard approaches based upon ILP formulations.

This paper explores the Gantry Cranes Scheduling Problem (GCSP), specifically focusing on determining the optimal slot unloading/loading sequences for gantry cranes assigned to containers in a block of stacking. The gantry crane scheduling proposed in this paper, which is mathematically modeled by a mixed integer programming model is proposed. using the terminal operating system used in the port studied provides a new (MILP). Finally, the paper compares the results obtained from the proposed model with those of the terminal port for real instances.

Time Expanded Networks, built by considering the nodes of a base network over some time space, are powerful tools for the formulation of problems involving synchronization mechanisms.Those mechanisms may for instance be related to the interaction between resource production and consumption or between routing and scheduling.Still, in most cases, deriving algorithms from those formulations is difficult, due to both the size of resulting network structure and the fact that reducing this size through rounding techniques tends to induce uncontrolled error propagation.We address here this algorithmic issue, while proposing a generic decomposition scheme which works by first skipping the temporal dimension of the problem and next expanding resulting projected solution into a full solution of the problem set on the time expanded network.

International audience

International audience

Time Expanded Networks, built by considering the vertices of a base network over some time space, are powerful tools for the formulation of problems that simultaneously involve resource assignment and scheduling. Still, in most cases, deriving algorithms from those formulations is difficult, due to both the size of the resulting models and the propagation of time rounding errors. The purpose of this paper is to address this algorithmic issue. We propose a generic Project and Lift decomposition scheme, and focus, inside this decomposition scheme, on the Lift issue, which consists in turning a solution defined on the base network into a solution in the time expanded space.

We make interact here 2 Knapsack players, which may be related to energy management or robot cooperation. We first discuss the setting of this problem and provide it with an ILP formulation. Next we deal with it through Dynamic Programming and deduce from this DP a Polynomial Time Approximation Scheme.

Managing autonomous vehicles inside restricted areas for internal logistics purpose raises the question of safety. We deal here with this issue, and propose a Safe Shortest Path model, which we handle first through tree search in a static context, and next through learning techniques in a dynamic context.

International audience

International audience

We deal here with a fleet of autonomous vehicles which is required to perform internal logistics tasks inside some protected area.This fleet is supposed to be ruled by a hierarchical supervision architecture, which, at the top level distributes and schedules Pick up and Delivery tasks, and, at the lowest level, ensures safety at the crossroads and controls the trajectories.We focus here on the top level, while introducing a time dependent estimation of the risk induced by the traversal of any arc at a given time.We set a model, state some structural results, and design, in order to route and schedule the vehicles according to a well-fitted compromise between speed and risk, a bi-level algorithm and a A* algorithm which both relies on a reinforcement learning scheme.

International audience

The emergence of H2energy produced through photolysis makes appear a new generation of local energy players, which are at the same time producers and consumers. This raises the question of synchronizing H2production, which deeply depends on the time, and its consumption through some transportation activity. We deal here with this issue, in the context of an experimental H2production platform, through dynamic programming augmented with ad hoc filtering devices.

Synchronizing heterogeneous processes remains a difficult issue in Scheduling area.Related ILP models are in trouble.So we propose here a pipe-line collaboration of a dynamic programming process for energy production and consumption scheduling.

We study a problem of scheduling unit-time jobs with given release dates and deadlines on identical parallel machines. No machine can stand idle between its start and completion times. The objective is to minimize the number of machines in use. A number of properties of this problem is established, and heuristic and optimal algorithms based on these properties are developed. They include optimal exponential algorithms for the general case and optimal polynomial algorithms for special cases. Lower and upper bounds are determined and an integer linear programming formulation is provided.

Managing a one-way vehicle sharing system means periodically moving free access vehicles from excess to deficit stations in order to avoid local shortages. While putting here the stress on routes followed by the vehicles while being exchanged between excess and deficit stations, we propose and study models and algorithmic approaches for a preemptive version of this problem which involves carrier riding cost, vehicle riding time and carrier number minimization. These approaches are based on the use of Layered Network.

International audience

Vehicle routing problems (VRP) concern the pickup and/or the delivery of goods from/to customers with vehicles. In the literature, most approaches consider the road network implicitly. Specifically, so‐called customer‐based graphs are used where nodes represent customers (plus the depot) and arcs represent best paths between customers. This model can affect solution quality when several attributes are defined on road segments (like travel time and distance). To handle that, two approaches are proposed in the literature. The road network can be represented using a multigraph that extends the customer‐based graph and where an arc is introduced for every efficient path between two nodes. Alternatively, the problem can be solved on a graph that mimics the original road network. In this paper, we investigate the latter approach. We consider the VRP with time windows (VRPTW) and we develop a branch‐and‐price scheme. An extensive computational study based on several types of instances is conducted in order to evaluate this approach compared to the multigraph‐based approach. As far as we know, our branch‐and‐price scheme is the first exact method for the VRPTW with the road‐network model. Also, our computational study provides the first comparison between the two models: multigraph and road‐network.

VIPAFLEET is a framework to develop models and algorithms for managing a fleet of Individual Public Autonomous Vehicles (VIPA). We consider a homogeneous fleet of such vehicles distributed at specified stations in a closed site to supply internal transportation, where the vehicles can be used in different modes of circulation (tram mode, elevator mode, taxi mode). We treat in this paper a variant of the Online Pickup-and-Delivery Problem related to the taxi mode by means of multicommodity coupled flows in a time-expanded network and propose a corresponding integer linear programming formulation. This enables us to compute optimal offline solutions. However, to apply the well-known meta-strategy Replan to the online situation by solving a sequence of offline subproblems, the computation times turned out to be too long, so that we devise a heuristic approach h-Replan based on the flow formulation. Finally, we evaluate the performance of h-Replan in comparison with the optimal offline solution, both in terms of competitive analysis and computational experiments, showing that h-Replan computes reasonable solutions, so that it suits for the online situation.

A recent evolution in urban logistics involves the usage of drones. In this article, we address a heuristic solution of the parallel drone scheduling traveling salesman problem, recently introduced by Murray and Chu. In this problem, deliveries are split between a vehicle and drones. The vehicle performs a classical delivery tour, while the drones are constrained to perform back and forth trips. The objective is to minimize completion time. We propose an iterative two‐step heuristic, composed of: a coding step that transforms a solution into a customer sequence, and a decoding step that decomposes the customer sequence into a tour for the vehicle and trips for the drones. Decoding is expressed as a bicriteria shortest path problem and is carried out by dynamic programming. Experiments conducted on benchmark instances confirm the efficiency of the approach and give some insights on this drone delivery system.

Vehicle routing problems have drawn researchers’ attention for more than 50 years. Most approaches found in the literature address these problems using the so‐called customer‐based graph, a complete graph representing the road network, where a node is introduced for every point of interest (eg, customers, depot…) and an arc represents the best path between two points. In many situations, this representation induces negative effects on the solution quality or efficiency. A growing number of works in the literature investigate these issues and propose modeling taking account of more detailed information from the road‐network. In this article, we review these works and classify them with respect to the type of negative effects provoked by the customer‐based graph.

The Vehicle Sharing Rebalancing Problem (VSRP) consists in the search for relocation strategies, for a fleet of free access vehicles, in a way which avoid shortages or bottlenecks. We deal here with a deterministic version of this problem, which embraces both preemptive and non preemptive cases. We first address the issue of getting both lower bounds and worst case approximation ratio. Next we propose heuristics and conclude with an experimental analysis.

Managing a one-way vehicle sharing system means periodically moving free access vehicles from excess to deficit stations in order to avoid local shortages.We perform a lower bound analysis for the static version of the resulting operational decision problem, and derive from this analysis two heuristic algorithms whose main feature is to be vehicle oriented, which means that they focus on the way vehicles are exchanged between excess and deficit stations. I.

Operating Vehicle Sharing systems means periodically performing some relocation process, in order to avoid stations becoming either empty or overfilled. We first propose here a static Vehicle Sharing Rebalancing (VSR) framework which unifies preemption and non preemption. Next we present and test a decomposition algorithmic scheme which decomposes our problem into a simple minimum cost assignment master problem and a slave PDP (Pick up and Delivery) problem.

Designing a vehicle sharing system means locating stations which allow users to pick up and give back vehicles.One takes this strategic level decision while anticipating related rebalancing costs.We study here a strategic related bi-level Vehicle Sharing Station Location (VSSL) model, which involves as slave problem a static Vehicle Sharing Rebalancing (VSR) model.

We deal here with the static version of decisional model related to real time monitoring of a DARP (Dial and Ride) system which involves, on a closed industrial site, small electrical autonomous vehicles. Because of technological issues, we focus on reliability, and propose a model which assigns requests to vehicles while minimizing Load/Unload transactions. We study this model through both a Branch/Price approach, which provides us with benchmarks, and insertion based heuristics, well-fitted to dynamic contexts.

This paper describes an efficient exact algorithm to solve the Resource Constrained Project Scheduling Problem (RCPSP). We propose an original and efficient branch and price procedure which involves minimal interval order enumeration as well as constraint propagation and which is implemented with the help of the generic SCIP software. We perform tests on the famous PSPLIB instances which provide very satisfactory results.

We address here a large scale routing and scheduling transportation problem, through introduction of a flow model designed on a dynamic network.We deal with this model while using a master/slave decomposition scheme, and testing the behavior on this scheme of both a GRASP algorithm and a Genetic algorithm.

We present here new results and algorithms for the Linear Arrangement Problem (LAP).We first propose a new lower bound, which links LAP with the Max Cut Problem, and derive a LIP model as well as a branch/bound algorithm for the general case.Then we focus on the case of interval graphs: we first show that our lower bound is tight for unit interval graphs, and derive an efficient polynomial time approximation algorithm for general interval graphs.I.