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.