METHOD FOR IMPROVING THE ROUTING OF A FLEET OF MODULAR ELECTRIC VEHICLES

Abstract

The invention provides a method for improving a delivery schedule for a fleet of modular electric vehicles, wherein each vehicle comprises a propulsion module having an electric propulsion system and a battery, and a set of trailer modules having a load capacity and a battery for providing electricity to said electric propulsion system, wherein each trailer module has an associated destination location and a destination time window. The proposed method is remarkable in that it is capable of taking into account multiple system constraints including random travel times using a genetic solving algorithm, and in that it is able to adapt the computation of delivery schedules to observed realizations of previously computed delivery schedules.

Claims

1. A method for improving delivery schedules for a fleet of modular electric vehicles, wherein each vehicle comprises a propulsion module having an electric propulsion system and a propulsion battery, and a set of trailer modules, wherein each trailer module has a load capacity and a trailer module battery for providing electricity to said electric propulsion system, wherein each trailer module has an associated destination location and a destination time window, the method comprising the steps of: a) computing a delivery schedule at a central computation unit starting at a common depot location, such that in accordance with said delivery schedule, each trailer module reach their respective destination locations within their respective destination time window given its available battery capacity, the delivery schedule being computed based on random variables that represent the expected travel times between any two destination locations that are sequentially visited by a vehicle; b) transmitting at least part of said delivery schedule to the respective vehicles of the fleet using a data transmission unit; wherein the probability distributions of said random variables are stored in a memory element of the central computation unit, and updated by said computation unit upon reception of an indication of the corresponding actual travel times experienced by said vehicles while driving in accordance with said delivery schedule, in order to take these travel times into account in future delivery schedule computations; and steps a) and b) are repeated at least once after the probability distributions of said random variables have been updated.

2. The method of claim 1, wherein said delivery schedule is computed by considering stops of the modular vehicles either at a destination location or at a recharging location, for recharging said electric propulsion batteries and/or trailer modules batteries.

3. The method of claim 1, wherein said random variables initially follow a log-Normal probability distribution.

4. The method of claim 2, wherein the initial delivery schedule, or any subsequent delivery schedule, is computed by the central computation unit by minimizing the objective function: $Min \underset{k \in V, i \in N_{0}}{.Math.} \underset{j \in N_{n + 1}, i \neq j}{.Math.} c_{i j}^{k} x_{i j}^{k} + c_{p} \underset{j \in N}{.Math.} \max {g_{j} - b_{j}, 0}$ $where$ $g_{i} = {\begin{matrix} a_{i} & if τ_{i} < a_{i} \\ τ_{i} & if τ_{i} \geq b_{i} \end{matrix}$ under a series of several constraints as follows: assignment constraints: $\begin{matrix} \underset{k \in V}{.Math.} \underset{i \in N_{n + 1}, i \neq j}{.Math.} x_{i j}^{k} = 1, \forall i \in C & (2) \\ \underset{k \in V}{.Math.} \underset{i \in N_{n + 1}, i \neq j}{.Math.} x_{i j}^{k} \leq 1, \forall i \in R & (3) \\ \underset{i \in N_{0}, i \neq j}{.Math.} x_{i j}^{k} - \underset{i \in N_{n + 1}, i \neq j}{.Math.} x_{j i}^{k} = 0, \forall i \in R & (4) \end{matrix}$ modular constraints: $\begin{matrix} λ_{p}^{m} \leq \underset{k \in V}{.Math.} \underset{j \in N, p \neq j}{.Math.} z_{p j}^{k m}, \forall m \in M, \forall p \in N & (5) \\ 1 \leq \underset{m \in M}{.Math.} z_{i j}^{k m} \leq N b_{\mod}, \forall k \in V, \forall i \in N_{0}, \forall j \in N_{n + 1} & (6) \end{matrix}$ time dependent constraints:
τ.sub.i+(max(s.sub.i,h.sub.i)+t.sub.ij)x.sub.ij.sup.k−b.sub.0(1−x.sub.ij.sup.k)≤τ.sub.j,∀k∈V,∀i∈N.sub.0,∀j∈N.sub.n+1,i≠j (7)
τ.sub.i+t.sub.ijx.sub.ij.sup.k+w.sup.k(E.sup.k−y.sub.i.sup.k)+(b.sub.0w.sup.kE.sup.k)(1−x.sub.ji.sup.k)≤τ.sub.j,∀k∈V,∀i∈N.sub.0,∀j∈N.sub.n+1,i≠j (8) capacity constraints:
0≤u.sub.j.sup.k≤u.sub.i.sup.k−q.sub.ix.sub.ij.sup.k+Q.sup.k(1−v.sub.ij.sup.k),∀k∈V,∀i∈N.sub.0,∀j∈N.sub.n+1,i≠j (9)
0≤u.sub.j.sup.k≤Q.sup.k,∀k∈V,∀j∈N.sub.0,n+1 (10) electric constraints $\begin{matrix} ϵ \leq y_{j}^{k} \leq y_{i}^{k} x_{i j}^{k} (1 - r_{i}^{k}) + r_{i}^{k} (w^{k} E^{k} + y_{i}^{k}) - e^{k} d_{i j} x_{i j}^{k}, \forall k \in V, \forall i \in N_{0}, \forall j \in N_{n + 1}, i \neq j & (11) \\ ϵ \leq y_{j}^{k} \leq E^{k} - (e^{k} d_{i j}) x_{i j}^{k}, \forall k \in V, \forall i \in N_{0}, \forall j \in N_{n + 1}, i \neq j & (12) \\ ϵ \leq y_{j}^{k} \leq E^{k} - \underset{m \in M}{.Math.} l_{i}^{m} z_{i j}^{k m}, \forall k \in V, \forall m \in M, i \neq j & (13) \\ y_{0}^{k} = E^{k}, \forall k \in V & (14) \end{matrix}$ and wherein the parameters and variables are defined as follows: Parameters: 0, n+1 Depot nodes; N Set of nodes, comprising the set of destination locations and recharging locations; V Set of modular vehicles; M Set of modules comprising propulsion modules and trailer modules; C Set of destination locations; R Set of recharging stations; R.sub.0 Set of recharging stations including the depot: d.sub.ij Distance between node i and node j; t.sub.ij Uncertain travel time between node i and node j; q.sub.i Demand at destination location i; a.sub.i Earliest start-window at destination location i; b.sub.i Latest start-window at destination location i; s.sub.i Service time at destination location i; h.sub.i Recharging time at destination location i; c.sub.ij.sup.k Travel cost of a vehicle of type k traversing the pair (i,j); c.sub.p Penalty per unit of time delay; e.sup.k Energy consumption per unit of traveled distance by a vehicle of type k; w.sup.k Energy recharging cost per unit of time for a vehicle of type k; E.sup.k Maximum energy capacity of a vehicle of type k; Nb.sub.mod Maximum number of modules to be added; Variables τ.sub.i Time variable specifying the time of arrival at destination location i; y.sub.i.sup.k Variable specifying the remaining charge of vehicle k at destination location i; l.sub.i.sup.m Variable specifying the remaining charge of module m at destination location i; u.sub.i.sup.k Variable specifying the remaining load of vehicle k at destination location i; g.sub.i Random starting time at node i; Decision variables x.sub.ij.sup.k Equal to 1 if a vehicle of type k travels from destination location i to destination location j, 0 otherwise; z.sub.ij.sup.km Equal to 1 if a vehicle of type k transports module m from node i to node j, 0 otherwise; λ.sub.i.sup.m Equal to 1 if destination location i is served by module m, 0 otherwise; r.sub.i.sup.k Equal to 1 if a vehicle of type k recharges at destination location i, 0 otherwise.

5. The method of claim 4, wherein minimization of said objective function comprises using the central computation unit to: draw S samples of said random variables, each sample being of size N and representing random arrival times at destination location and/or recharging locations, and storing said samples in a memory element; compute S values of said objective function ƒ.sub.N.sup.1, ƒ.sub.N.sup.2, . . . ƒ.sub.N.sup.S, by solving the problem (1) repeatedly using a genetic algorithm; compute an average value of the optimal solutions as $= \frac{1}{S} {.Math.}_{S = 1}^{S} f_{N}^{S} ({\tilde{x}}^{S}, {Sa}_{S} (p),$ wherein {tilde over (x)}.sup.1, {tilde over (x)}.sup.2, . . . {tilde over (x)}.sup.S are candidate solutions, and Sa.sub.h(p) is the h-th sampling of the stochastic parameters.

6. The method of claim 1, wherein each modular vehicle transmits information providing an indication of the actual residual trailer module battery charge of each module to the central computation unit at least once as it drives in accordance with the delivery schedule.

7. The method of claim 1, wherein only data describing a specific vehicle's route, as provided by a computed delivery schedule, is transmitted to the corresponding vehicle.

8. The method of claim 1, further comprising the step of: autonomously driving the modular vehicle in accordance with said delivery schedule.

9. The method of claim 1, further comprising the step of: displaying at least part of said delivery schedule on a display unit in the modular vehicle.

10. The method of claim 1, wherein the indication of the corresponding actual travel times experienced by a respective vehicle is measured by a timing unit of the vehicle and transmitted to the central computing unit by the vehicle.

11. A computing device comprising a data processing unit, a data transmission unit and at least one memory element operatively connected to the data processing unit, wherein data describing a fleet of modular electric vehicles, each vehicle comprising a propulsion module having an electric propulsion system and a propulsion battery, and a set of trailer modules, wherein each trailer module has a load capacity and a trailer module battery for providing electricity to said electric propulsion system, is provided in a memory element; data describing a plurality of destination locations and destination time windows is provided in a memory element, wherein said trailer units are associated with said destination locations and time windows; data describing a delivery schedule starting at a common depot location, such that each trailer module reaches their respective destination location within their respective destination time window given its available battery capacity is provided in a memory element; wherein the data transmission unit is configured to transmit at least part of said delivery schedule to the respective vehicles of the fleet; and further wherein the delivery schedule is based on random variables that represent the expected travel times between any two destination locations that are sequentially visited by a vehicle, and in that the data processing unit is configured for updating said probability distributions of said random variables upon reception of an indication of the corresponding actual travel times experienced by said vehicles while driving in accordance with said delivery schedule, in order to take these travel times into account in future delivery schedule computations; the data processing unit is configured for calculating at least one further delivery schedule after the probability distributions of said random variables have been updated, and for transmitting at least part of said delivery schedule to the respective vehicles of the fleet.

12. The computing device of claim 11, wherein the data processing unit is further configured to perform the method steps in accordance with claim 2.

13. A computer program comprising computer readable code, which when run on a computer, causes the computer to carry out the method according to claim 1.

14. A computer program product comprising a computer-readable medium on which the computer program according to claim 13 is stored.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0087] Several embodiments of the present invention are illustrated by way of figures, which do not limit the scope of the invention, wherein:

[0088] FIG. 1 illustrates the concepts in accordance with a preferred embodiment of the method and system in accordance with the invention;

[0089] FIG. 2 illustrates routes as provided by a delivery schedule generated by a preferred embodiment of the method in accordance with the invention;

[0090] FIG. 3 illustrates a chromosome or candidate solution as provided by the genetic algorithm used in accordance with embodiments of the invention.

DETAILED DESCRIPTION OF THE INVENTION

[0091] This section describes aspects of the invention in further detail based on preferred embodiments and on the figures. The figures do not limit the scope of the invention.

[0092] An example of a system in which the invention is used is illustrated in FIG. 1. The invention considers a fleet 100 modular electric vehicles 110, 120 for urban distribution of goods. Indeed, this concept is founded on a modular and active frame design for the vehicle which allows the first module, called a propulsion or cabin module 112, 122, to carry one or multiple modules in order to bring more commodities. First, a modular vehicle is as its name suggests, made up of a cabin/propulsion module managed by a driver, followed by a (possibly empty) set of trailer units 114, 124. Alternatively, the propulsion module may be configured for autonomous driving. Typically, the propulsion module is equipped with an electrical motor driving at least one axle. The electrical motor is coupled to the batteries of each of the vehicle's modules. The propulsion module may be pushing the trailer unit or towing them. It is equipped with a computing device and data transmission/reception means, for communicating with a remote central computing unit 200. Each module 112, 114, 122, 124 has its own battery and is autonomous in terms of consumption and electric charging. Moreover, it may be assumed that the modules can be of the same volume and therefore carry the same amount of goods.

[0093] FIG. 2 describes possible solutions related with new logistics schemes for urban distribution using electric modular vehicles. One solution is defined by the solid-lined route. First, the vehicle leaves the depot with utmost three modules, serves the first customer at 10 AM and releases the last module at this customer location. Thereafter, it visits the next customer who has to be served at 11 AM, and releases there another payload module. In this case, the vehicle performs the rest of its tour with only one module. Then, the vehicle has to serve another customer before 1 PM. When it reaches this location, it retrieves a module let by another modular vehicle earlier in the day and pursues its route with two payload modules. Thereafter, it goes to another customer who should be delivered at 12 AM. It releases there a payload module and returns to the depot with only the cabin module. At the end of the studied period, all the modules (propulsion and trailer units) should be back to the depot.

[0094] Given a set of customers associated with destination locations, which have known demands, and a heterogeneous fleet of electric modular vehicles starting from a localized depot, the aim is to compute routes that begin and end at this depot, such that all the needs at the destination locations are fulfilled and the capacity of the fleet as well as the timing constraints are respected.

[0095] Formally, let G=(N,A) be a complete directed graph where N denotes a set of nodes. We have N=C∪R consisting of a set of destination locations C and a set of recharging stations R. Further, let nodes 0 and n+1 represent the beginning and end of the tour respectively, i.e., N={0}∪{1, . . . , n}∪{n+1}. Thus, let A.Math.N×N, denotes the arc set with A={(i,j)|i,j∈N,i≠j}. Each arc (i,j) is associated with an uncertain travel time t.sub.ij and a distance d.sub.ij. Each vehicle of type k, when it crosses an arc, consumes the amount e.sup.kd.sub.ij of the remaining battery charge, where e.sup.k denotes the energy consumption per distance unit travelled. A fleet of heterogeneous vehicles is stationed at the depot. Before leaving, each electric vehicle must be fully charged at the maximum recharge quantity E.sup.k. Each customer located at node i∈N has a positive demand q.sub.i, a service time s.sub.i, a time window [a.sub.i,b.sub.i] and a recharging time h.sub.i. The proposed model is based on the use of electric vehicles. For this reason, planning a trip with these vehicles requires the consideration of some assumptions linked with both the charging infrastructure and the charging policy.

[0096] Some hypothesis have been set in order to define properly the problem. These assumptions are related basically to the recharging policy. [0097] The depot can be used as a recharging station and all the vehicles must be fully charged when they leave the depot. Vehicles may need to recharge their battery at customer locations in order to continue a tour. [0098] The vehicle recharges at a customer location if the battery charge level drops below a given threshold. [0099] Recharging at customer locations requires a joint agreement with owners, in respect to rates and to charging times. [0100] The recharging time depends on the remaining energy when arriving at the recharging station. [0101] If the service time is not yet finished, the vehicle remains in charge even if the charge level of the battery is above the threshold. Otherwise, if it is below the threshold, the vehicle will recharge until this threshold and a penalty is added to the objective function.

[0102] The arrival time at destination locations are modelled as random variables. The random variables may be drawn in accordance with a log-Normal probability distribution, which has been shown to provide a good match for modelling travel times in urban traffic. As will be explained, the probability distributions are preferably adapted over time, so that the computational model is refined and more closely matches the settings encountered by the modular electric vehicles.

[0103] In what follows, it is proposed that a delivery schedule, comprising delivery routes for all modular vehicles 110, 120 of a fleet 100, is computed at a central computation unit. Reference is made to FIG. 1. The computation unit 200 may be a single computing device configured through appropriate software to resolve the delivery routing problem that will be set out here below. Alternatively, the computation unit may be provided as a cluster of distributed computing devices, which interact using a data communication network. The computation unit has access to memory elements in which data describing a fleet of modular electric vehicles, wherein each vehicle comprises a propulsion module having an electric propulsion system and a battery, and a set of trailer modules having a load capacity and a battery for providing electricity to said electric propulsion system. Each trailer module 114, 124 has an associated destination location and a destination time window:

[0104] An initial delivery schedule 10 is provided at the central computing unit. The initial schedule may be computed by solving the problem set out here below, or it may be pre-stored in a memory element 250 and read therefrom by the computing unit. The initial delivery schedule is based on random travel times for each route connecting two subsequent destination locations. The delivery schedule comprises routes for each vehicle 110, 120 of the fleet, starting at a common depot location, such that in accordance with said delivery schedule, each trailer module 114, 124 should reach its destination location within its destination time window given its available battery capacity.

[0105] At least part of said delivery schedule 10 is transmitted from the computing unit to the respective vehicles of the fleet. This is depicted by step b) in FIG. 2. Preferably, only the route (i.e., sequence destination location) that is assigned to a given vehicle is transmitted to that particular vehicle, which may preferably display it on a display unit, or which may use it as an input to a navigation system or to guide an autonomous driving system.

[0106] The initial delivery schedule 10 is computed based on random variables that represent the expected travel times between any two destination locations that are subsequently visited by a vehicle. The probability distributions of said random variables are stored in a memory element 250 of the central computation unit, and updated by said computation unit upon reception, using a data receiving unit 240, of an indication of the corresponding actual travel times t-110, t-120 experienced by said vehicles 110, 120 while driving in accordance with said delivery schedule 10, in order to take these travel times into account in future delivery schedule computations. The travel times may be logged and transmitted to the central computation unit by clocks in the vehicles themselves, or the fleet may be monitored by a satellite geo-positioning system, from which arrival/travel times may be inferred. For example, the central computing unit may keep a histogram in a memory element for each pair of destination locations, in which observed travel times for the corresponding route are counted. The non-empty bins of the resulting histogram may be combined, for example through a weighting function, with the corresponding samples of the log-Normal probability distribution. While maintaining features of the theoretical model, this combination with real-world observations allows the system to take into account systematic variations in the travel times on a given route, which may arise due to peak traffic hours, road works or weather conditions. As the travel-time updates are preferably gathered each time the fleet is operational, an up-to-date dynamic profile of the overall travel times may be obtained without resorting to actual geographical routing data or external traffic information sources. By using the updated probability distributions for future computations, the resulting future delivery schedules 10 will be more accurate and they will result in a more efficient use of the available electrical energy and load capacity.

[0107] In accordance with embodiments of the invention, the feedback t-110, t-120 provided by the actual implementation of a computed delivery schedule, may further include other observed parameters, such as the observed residual battery charges for each module at each destination. This allows the central computation 200 unit to rely on up-to-date date and battery capacities in future delivery schedule computations. This approach may for example implicitly be used to take into account (or identify) a diminished maximum capacity of a battery, or a battery that drains faster than expected. This information is exploited by the computation unit to provide more accurate future delivery schedules, but it may as well be used to detect maintenance need of the electric modules.

[0108] The problem solved by aspects of the invention may be formalized as follows: [0109] Parameters: [0110] 0, n+1 Depot nodes; [0111] N Set of nodes, comprising the set of destination locations and recharging locations; [0112] V Set of modular vehicles; [0113] M Set of modules comprising propulsion modules and trailer modules; [0114] C Set of destination locations; [0115] R Set of recharging stations; [0116] R.sub.0 Set of recharging stations including the depot: [0117] d.sub.ij Distance between node i and node j; [0118] t.sub.ij Uncertain travel time between node i and node j; [0119] q.sub.i Demand at destination location i; [0120] a.sub.i Earliest start-window at destination location i; [0121] b.sub.i Latest start-window at destination location i; [0122] s.sub.i Service time at destination location i; [0123] h.sub.i Recharging time at destination location i; [0124] c.sub.ij.sup.k Travel cost of a vehicle of type k traversing the pair (i,j); [0125] c.sub.p Penalty per unit of time delay; [0126] e.sup.k Energy consumption per unit of traveled distance by a vehicle of type k; [0127] w.sup.k Energy recharging cost per unit of time for a vehicle of type k; [0128] E.sup.k Maximum energy capacity of a vehicle of type k; [0129] Nb.sub.mod Maximum number of modules to be added; [0130] Variables [0131] τ.sub.i Time variable specifying the time of arrival at destination location i; [0132] y.sub.i.sup.k Variable specifying the remaining charge of vehicle k at destination location i; [0133] l.sub.i.sup.m Variable specifying the remaining charge of module m at destination location i; [0134] u.sub.i.sup.k Variable specifying the remaining load of vehicle k at destination location i; [0135] g.sub.i Random starting time at node i; [0136] Decision variables [0137] x.sub.ij.sup.k Equal to 1 if a vehicle of type k travels from destination location i to destination location j, 0 otherwise; [0138] z.sub.ij.sup.km Equal to 1 if a vehicle of type k transports module m from node i to node j, 0 otherwise; [0139] λ.sub.i.sup.m Equal to 1 if destination location i is served by module m, 0 otherwise; [0140] r.sub.i.sup.k Equal to 1 if a vehicle of type k recharges at destination location i, 0 otherwise.

[0141] Mathematical Formulation

[0142] Minimization of the Objective Function

[00006] $\begin{matrix} Min {.Math.}_{k \in V, i \in N_{0}} {.Math.}_{j \in N_{n + 1}, i \neq j} c_{i j}^{k} x_{i j}^{k} + c_{p} {.Math.}_{j \in N} \max {g_{j} - b_{j}, 0} Where g_{i =} {\begin{matrix} a_{i} & if τ_{i} < a_{i} \\ τ_{i} & if τ_{i} \geq b_{i} \end{matrix} & (1) \end{matrix}$

[0143] Under a series of several constraints as follows: [0144] Assignment constraints

[00007] $\begin{matrix} \underset{k \in V}{.Math.} \underset{i \in N_{n + 1}, i \neq j}{.Math.} x_{i j}^{k} = 1 \forall i \in C & (2) \\ \underset{k \in V}{.Math.} \underset{i \in N_{n + 1}, i \neq j}{.Math.} x_{i j}^{k} \leq 1 \forall i \in R & (3) \\ \underset{i \in N_{0}, i \neq j}{.Math.} x_{i j}^{k} - \underset{i \in N_{n + 1}, i \neq j}{.Math.} x_{j i}^{k} = 0 \forall i \in R & (4) \end{matrix}$ [0145] Modular constraints

[00008] $\begin{matrix} λ_{p}^{m} \leq \underset{k \in V}{.Math.} \underset{j \in N, p \neq j}{.Math.} z_{p j}^{k m} \forall m \in M, \forall p \in N & (5) \\ 1 \leq \underset{m \in M}{.Math.} z_{i j}^{k m} \leq N b_{\mod} \forall k \in V, \forall i \in N_{0}, \forall j \in N_{n + 1} & (6) \end{matrix}$ [0146] Time dependent constraints

τ.sub.i+(max(s.sub.i,h.sub.i)+t.sub.ij)x.sub.ij.sup.k−b.sub.0(1−x.sub.ij.sup.k)≤τ.sub.j ∀k∈V,∀i∈N.sub.0,∀j∈N.sub.n+1,i≠j (7)

τ.sub.i+t.sub.ijx.sub.ij.sup.k+w.sup.k(E.sup.k−y.sub.i.sup.k)+(b.sub.0w.sup.kE.sup.k)(1−x.sub.ji.sup.k)≤τ.sub.j ∀k∈V,∀i∈N.sub.0,∀j∈N.sub.n+1,i≠j (8) [0147] Capacity constraints

[00009] $\begin{matrix} 0 \leq u_{j}^{k} \leq u_{i}^{k} - q_{i} x_{i j}^{k} + Q^{k} (1 - x_{i j}^{k}) \forall k \in V, \forall i \in N_{0}, \forall j \in N_{n + 1}, i \neq j & (9) \\ 0 \leq u_{j}^{k} \leq Q^{k} \forall k \in V, \forall j \in N_{0, n + 1} & (10) \end{matrix}$ [0148] Electric constraints

[00010] $\begin{matrix} ϵ \leq y_{j}^{k} \leq y_{i}^{k} x_{i j}^{k} (1 - r_{i}^{k}) + r_{i}^{k} (w^{k} E^{k} + y_{i}^{k}) - e^{k} d_{i j} x_{i j}^{k} \forall k \in V, \forall i \in N_{0}, \forall j \in N_{n + 1}, i \neq j & (11) \\ ϵ \leq y_{j}^{k} \leq E^{k} - (e^{k} d_{i j}) x_{i j}^{k} \forall k \in V, \forall i \in N_{0}, \forall j \in N_{n + 1}, i \neq j & (12) \\ ϵ \leq y_{j}^{k} \leq E^{k} - \underset{m \in M}{.Math.} l_{i}^{m} z_{i j}^{k m} \forall k \in V, \forall m \in M, i \neq j & (13) \\ y_{0}^{k} = E^{k} \forall k \in V & (14) \end{matrix}$

[0149] Constraint (2) ensures that each customer is served exactly once and exactly by one vehicle while constraint (3) ensures that each recharging station will have at most one successor node: a customer, a recharging station or the depot. Furthermore, constraint (4) ensures that for each node, the number of arrivals must equal the number of departures. In addition, the constraint described in (5) ensures that if the module m serves customer p, then module m should leave customer p to serve customer j. In constraint (6) we enforce that each vehicle may carry a predefined number of modules at most at any given time and to move forward the cabin module, the vehicle should at least bring one payload module. The problem may alternatively be solved in order to determine the maximum number of modules per vehicle given the remaining constraints. Constraints (7) and (8) guarantee the elimination of subtours. Moreover, constraints (9) and (10) are dedicated to capacity constraints. The constraint depicted in (9) ensures that the load at node j depends on the load at node i which takes into account the demand q.sub.i, while constraint (10) ensures that the load u.sup.k.sub.j should not exceed the capacity Q.sup.k of the vehicle. Thereafter, the electric constraints are described by the constraints (11)-(13). Constraint (11) ensures that the charge level of the vehicle in the node j depends on the energy consumed when it crosses the arc (i,j). Constraint (12) specifies that the remainder of the charge in node j is equal to the maximum load of the battery less the charge consumed along the arc (i,j). Constraint (13) ensures that the level of electrical charge of the overall vehicle including the attached modules must not fall below a given threshold. Finally, in (14) we enforce that the vehicle must be fully charged when it leaves the depot.

[0150] An instance of this model may for example be resolved using the commercially available solver called Cplex™, which uses the Branch and Bound technique to solve the problem.

[0151] Preferably, instances of the model may be solved by resorting to a genetic algorithm. In recent decades, several studies were conducted to compare the genetic algorithms, GA, to other metaheuristic algorithms. The most important advantage of GA compared to other metaheuristic approaches is that GA proved to be an efficient method by outputting adequate (good enough) solutions and good results in an acceptable time. For that reason, genetic algorithms are well used to solve combinatorial optimization problem and especially NP hard problems. Therefore, it is proposed to chose the genetic algorithm that has already proven its performance on routing transportation problems, see S. Karakatic and V. Podgorelec, “A survey of genetic algorithms for solving multi depot vehicle routing problem” Applied Soft Computing, vol. 27, pp. 519-532, 2014, and H. Nazif and L. S. Lee, “Optimized Crossover Genetic Algorithm for Vehicle Routing Problem with Time Windows” American Journal of Applied Sciences, vol. 7, no. 1, pp. 95-101, 2010.

[0152] In practice, there are several ways to generate an initial population, to select the best individual from the population and to diversify the population over generations. However, all GA methods should have a good representation of an individual, appropriate evaluation function and especially good genetic operators.

[0153] A. Genetic Representation and Encoding

[0154] Like in most GAs for Vehicle Routing problems, see for example, S. Tasan and A. M. Gen, “A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries” Computers and Industrial Engineering, vol. 62, pp. 755-761, 2012 or Z. Wang, H. Duan and X. Zhang, “An Improved Greedy Genetic Algorithm for Solving Travelling Salesman Problem” IEEE International Conference on Natural Computation, vol. 5, pp. 374-378, 2009, a chromosome or candidate solution is represented with an array of n customer nodes which are served by the vehicles. This representation appears to be the most used and the simplest one. However, the weakness of this permutation is that there is no indication from which route and with which vehicle the customer is served. Therefore, we have chosen to use the representation depicted in FIG. 3 complemented with the depot index 0 in the genotype. The provided example is unrelated to the routes depicted in FIG. 2.

[0155] An integer sequence [1, . . . , 13] represents the destination locations while the index 0 is dedicated to the depot. Route 1 of vehicle V1 starts at the depot, visits customers 1, 2, 3, 4 and 5 and goes back to the depot. Route 2 of vehicle V2 starts from the depot to customers 6, 7, 8 and 9. Finally, route 3 of vehicle V3 begins from the depot and visits the last four customers 10 to 13. Each vehicle is characterized by its set of attached modules, its state of charge, its uncertain arrival time, its travel time and the remaining load.

[0156] B. Initial Population Construction

[0157] To generate an initial population, a constructive heuristic is used in order to create a list of customers visited by each vehicle. One popular way to generate an initial solution is to use a greedy algorithm. The main idea is to start from an empty initial solution and add incrementally the solution components taking into account the previous choices until a complete solution is obtained. It is proposed to choose at each step the nearest customer to the customers already visited, while ensuring that capacity constraints as well as timing constraints are respected. The greedy algorithm provides a single initial solution. Therefore, to generate an initial population, an improvement heuristic called 2-opt exchange is proposed, which consists of eliminating two edges from our initial solution obtained by the greedy algorithm and reconnecting the two resulting routes differently to obtain a new path. Thus, the heuristic 2-opt exchange can modify differently the route by rearranging a pair of edges. The other characteristics of the used genetic algorithm are as follows.

[0158] C. Fitness Function

[0159] The fitness function measures the quality of the represented solutions. Once individuals are created, they are ranked as per their fitness value calculated as the sum of the total distance travelled, and the penalty costs.

[0160] D. Selection

[0161] The tournament selection is used in our proposed approach, where the numbers of randomly picked individuals compete in the tournament. The main idea consists in running several tournaments among a few individuals randomly selected from the population. The best individuals of each tournament with the best fitness value are selected to generate new offsprings in the next phase.

[0162] E. Crossover

[0163] Crossover is the process that allows in nature the production of chromosomes, which partially inherit the characteristics of the parents in order to produce offsprings. In this purpose, we are interested to apply a Partial Mapping Crossover, PMX, because it has the advantage of providing best solutions in a short time frame among others operators.

[0164] F. Mutation

[0165] The mutation always improves the search process by helping to escape from local minima. Therefore, the insertion mutation is proposed, where the main idea is to remove the node from its place and insert it at another randomly chosen place on the route or possibly in another different route.

[0166] In order to adapt the genetic algorithm to the stochastic travelling times, a sample average approximation approach is proposed. Therein, the minimization of objective function (1) comprises using the central computation unit to: [0167] draw S samples of said random variables, each sample being of size N and representing random arrival times at destination location and/or recharging locations, and storing said samples in a memory element; [0168] compute S values of said objective function ƒ.sub.N.sup.1, ƒ.sub.N.sup.2, . . . ƒ.sub.N.sup.S, a by solving the problem (1) repeatedly using a genetic algorithm; [0169] compute an average value of the optimal solutions as

[00011] $= \frac{1}{S} {.Math.}_{S = 1}^{S} f_{N}^{S} ({\tilde{x}}^{S}, {Sa}_{S} (p),$

wherein {tilde over (x)}.sup.1, {tilde over (x)}.sup.2, . . . {tilde over (x)}.sup.S are candidate solutions, and Sa.sub.h(p) is the h-th sampling of the stochastic parameters.

[0170] The candidate solutions are obtained by applying the genetic algorithm to the problem in which the travel times are replaced by stochastic values respecting the log-normal (or correspondingly updated) probability distribution.

[0171] It should be noted that features described for a specific embodiment described herein may be combined with the features of other embodiments unless the contrary is explicitly mentioned.

[0172] Based on the description and figures that has been provided, a person with ordinary skills in the art will be enabled to develop a computer program for implementing the described methods without undue burden.

[0173] It should be understood that the detailed description of specific preferred embodiments is given by way of illustration only, since various changes and modifications within the scope of the invention will be apparent to the person skilled in the art. The scope of protection is defined by the following set of claims.

METHOD FOR IMPROVING THE ROUTING OF A FLEET OF MODULAR ELECTRIC VEHICLES

Assignee

Inventors

Cpc classification

Classification Explorer

G06Q50/30

PHYSICS

Classification Explorer

G06Q10/047

PHYSICS

Classification Explorer

G07C5/008

PHYSICS

Classification Explorer

G06Q10/06314

PHYSICS

Classification Explorer

G06Q10/083

PHYSICS

Classification Explorer

G06Q50/28

PHYSICS

Classification Explorer

B60W60/00256

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

G06Q10/06312

PHYSICS

International classification

Classification Explorer

G06Q50/28

PHYSICS

Classification Explorer

B60W60/00

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

G06Q10/06

PHYSICS

Classification Explorer

G07C5/00

PHYSICS

Abstract

Claims

Description