Please excuse me for the long question, if I dont prrovide this info. my post gets removed!

The following optimization problem is called Mixed-Integer Quadratically Constrained Programming (MIQCP) problem in the research paper, "Optimal Routing and Charging of an Electric Vehicle Fleet for High-Efficiency Dynamic Transit Systems".

Let us say there is a graph (traffic network map of a town) like below:

enter image description here

enter image description here

We would like to find optimal route from start node to passenger pickup to passenger delivery location to end node by travelling through nodes in the network.

The objective function is given below.

enter image description here

The decision variable is $x_{ij}^k$ which is a binary variable 1 or 0 for taking a route from node i to j using Electric Vehicle (EV) k.

The first term in the objective is trying to miniize the distance travelled between pickup and delivery for all the EVs.

The second term is minimizing travel time for all EVs. one EV k only carries one passenger i.

The third term is minimizing the charging cost of all the EVs.

Legend is given below:

enter image description here

enter image description here

Now my question is regarding the constraints.

enter image description here

What does $j \in P \cup D \oplus {e_k}$ mean?

In constraint 6, destination node j is a node that can be from 'either' pickup/delivery nodes 'or' end node of vehicle k. why not just use union instead of xor (either or)?

Also why is enter image description here also xor and not union?

if it is xor then do we have to think of this as two seperate cases when $i \not\in {s_k} $ in first case and $i \not\in {e_k} $ in second case?

Could you please explain the physical meaning constraint 8?

i is either from P or D or intermediate node. j can be any node. sum over all j nodes to a particular node i for a vehicle k which can be more than 1 minus route from r to i which can only be 1 or 0. This is bounded by enter image description here and enter image description here

I dont understand the explanation from the paper below: maybe you might find it useful. enter image description here

Why is it called "Quadratically Constrained" ? I don't see any squared terms in the constraints.

The remaining constraints are given below.

enter image description here

enter image description here

  • 1
    $\begingroup$ Cross-posted at math.stackexchange.com/questions/4255177/…. $\endgroup$
    – prubin
    Commented Sep 20, 2021 at 15:51
  • $\begingroup$ "I don't see any squared terms in the constraints." See eq 15. $\endgroup$ Commented Sep 20, 2021 at 16:32
  • $\begingroup$ @ErwinKalvelagen. thanks. what is the physical meaning of the two equations in (15)? what is the difference between EV m and n ? Is it like this? say m and n are any two EVs at charging station i, first equation of 15 says that EV n arrives before EV m. the time when n finishes charging after arrival and waiting of m should be below a threshold? The x term in the threshold is the sum over all nodes we could possible go to from this charging node. so if we had more options to go to many nodes from i then threshold is larger? why is there $1 - \sum(x)$? is M a large positive number? $\endgroup$ Commented Sep 20, 2021 at 19:49
  • $\begingroup$ Please explain the threshold on the right hand side of equation 15. $\endgroup$ Commented Sep 20, 2021 at 19:50
  • $\begingroup$ Sorry, I did not read the paper. I just scanned the constraints. $\endgroup$ Commented Sep 20, 2021 at 19:53


Your Answer

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