8
$\begingroup$

Given a set of Vehicles with source and destination I need to find the minimum time of travel for all the vehicles, there are also some charging stations and its necessary for vehicles to charge 1 time at any of the charging stations

I have the following input:

1.) Vehicles source and destination pair ([(1, 15), (16, 25), (6, 5)])

2.) Charging station [12, 8, 13, 18]

Image of charging station no. 12

Image of charging station no. 12

Image of charging station no. 18

Image of charging station no. 18

In the Image $node_i$ denote the vehicle source, start is the time to reach from source to the charging station, charge is the time to charge at that charging station, destination is the time to reach from charging station to their respective destination, total is the sum of all time.

I need to find an allocation of vehicles to the charging station so that total time is minimum.

If a vehicle is charging at a charging station and at the same time any other vehicle arrives, it needs to wait until charging station is free.

I tried a greedy approach in which I wrote values in a matrix.

Greedy Matrix

Greedy Matrix of total time from charging station tables.

In this, vehicles are the rows, charging stations are the columns, and the bold ones are the minimum of each row, therefore, I choose them. But, vehicles 1,6 are allocated to charging station 8, which means there can be some waiting time. After checking their start and charging time, the new matrix is formed.

updated Greedy Matrix

Updated Greedy Matrix

As you can see vehicle 1 value is updated from 1.21 to 1.63. Now, it's better to allocate 1 to charging station 13 because now it has the minimum time. But again, it may need to wait because charging station 13 already has 16 allocated to it.

What is the approach to solve this kind of problem?

EDIT 1:

After suggestions from @prubin I have created these equation.

$V$ is set of vehicles.

$S$ is the set of charging stations.

$src$ source time.

$ch$ charging time.

$dst$ destination time.

$wt$ waiting time.

$b$ boolean variable for deciding if v is allocated to s or not.

$$ \sum_{v \in V} \sum_{s \in S} (src_{v,s} + ch_{v,s} + dst_{v,s} + wt_{v,s}) * b_{v,s} $$

$$ \forall i \in V \hspace{0.3cm} \forall j \in V \hspace{0.3cm} \forall s \in S \hspace{0.3cm} wt_{j,s} \geq ((src_{i,s} + ch_{i,s}) - src_{j,s}) * x_{ij} $$

$$ \forall v \in V \sum_{s \in S} b_{v,s} = 1 $$

$$ \sum_{v \in V} \sum_{s \in S} b_{v,s} = |V| $$

I can't figure out way to include non overlapping condition and if multiple vehicles are allocated to the same station how to update $CH$ value in equation.

$\endgroup$

1 Answer 1

12
$\begingroup$

You can solve this with a mixed integer linear program. It has some similarities to job shop scheduling (with parallel machines) and multiprocessor scheduling, although it is not identical to either. In one approach, you create continuous variables for each vehicle representing the time the vehicle begins charging, the time it ends charging, and the time it reaches its destination. You add binary variables for each combination of vehicle and charging station, and constraints tying those variables to the continuous variables. Those constraints look like "if vehicle 1 charges at station 12 then charging of vehicle 1 ends ... minutes after it starts and arrival at destination is ... minutes after charging ends."

That leaves the issue of nonoverlap at charging stations, which leads to more binary variables. You can create a binary variable $x_{ij}$ for each pair $i \neq j$ of vehicles, such that $x_{ij}=1$ means that $i$ charges before $j$ if they are at the same charging station. Then you need constraints that relate the time each vehicle starts charging to the time the other vehicle ends charging and the correct $x$ variable.

$\endgroup$
16
  • $\begingroup$ charging time changes when two or more vehicles are allocated to the same charging station. How this is handled? $\endgroup$
    – ooo
    Jul 28, 2019 at 18:29
  • $\begingroup$ I have adding equations in my question as per your suggestion but how do I include non overlapping conditions. $\endgroup$
    – ooo
    Jul 29, 2019 at 15:26
  • $\begingroup$ You originally said vehicles had to wait if a charging station is occupied. Are you saying now that vehicles can overlap, but that it affects the charging time? Or that vehicles cannot overlap AND charging time is affected by other vehicles? If the latter, HOW is charging time affected? $\endgroup$
    – prubin
    Jul 29, 2019 at 20:08
  • $\begingroup$ for ex if V1, V2 allocated to S1 and V1 arrives at time 2 and start charging and finishes charging at 10 (8 unit time of charging), V2 arrives S1 at time 5 and needs total charging time 6 unit so V2 can only start after time 10 when V1 leaves so V2 starts at time 10 and leaves at time 16 (6 unit time of charging, 5 unit time of waiting). $\endgroup$
    – ooo
    Jul 30, 2019 at 3:53
  • $\begingroup$ So the time actually charging is not changed; there is just some waiting time. That does not change my original answer. $\endgroup$
    – prubin
    Jul 31, 2019 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.