# vehicle routing optimization, Big M method of reformulation of constraints

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:  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. 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:  Now my question is regarding the constraints. 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 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 and I dont understand the explanation from the paper below: maybe you might find it useful. Why is it called "Quadratically Constrained" ? I don't see any squared terms in the constraints.

The remaining constraints are given below.  • Cross-posted at math.stackexchange.com/questions/4255177/…. Sep 20 at 15:51
• "I don't see any squared terms in the constraints." See eq 15. Sep 20 at 16:32
• @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? Sep 20 at 19:49
• Please explain the threshold on the right hand side of equation 15. Sep 20 at 19:50
• Sorry, I did not read the paper. I just scanned the constraints. Sep 20 at 19:53