Finding minimum time for vehicle to reach to its destination

Question

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. 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 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

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.

Answer 1

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.