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.

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

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.

International audience

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

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.