I am trying to solve a multi-objective vehicle routing problem, I want to implement a lexicographic objective function, I have already defined a function for each objective. if someone has an idea of how can implement the lexicographic function. (PS. the code is written in python).
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Are you using Gurobi/CPLEX? $\endgroup$– dxbCommented Sep 29, 2021 at 20:00
-
$\begingroup$ yes I have the result of the CPLEX, but I want to compare it with a heuristic I have implemented $\endgroup$– Nada.SCommented Sep 29, 2021 at 20:06
-
$\begingroup$ To clarify: you are asking how to implement the objective function in your heuristic, rather than how to implement it using CPLEX, correct? Does you heuristic require a single number as objective value, or is it sufficient to provide a function that lets the heuristic compare two solutions and see which is preferable? $\endgroup$– prubin ♦Commented Sep 29, 2021 at 21:08
-
$\begingroup$ For the first one correct, for the second yes the heuristic requires a single value but it must have the same representation of the lexicographic function of CPLEX. I need to compare the value of the solution given by the CPLEX and the one given by the heuristic. $\endgroup$– Nada.SCommented Sep 29, 2021 at 21:41
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Let $f(x)=(f_1(x),f_2(x),\dots,f_n(x))$ be a lexicographic objective function, where $f_1(x)$ is more important than $f_2(x)$ which in turn is more important than $f_3(x)$, etc. I'll assume you are solving a minimization problem. In a mathematical programming solver, such an objective function could be easily implemented as follows. First find the solution $x$, subject to $x\in X$ which scores best on objective $f_1$ (here $X$ is the set of feasible solutions). Next, find the solution $x'$ that scores best on objective f_2, subject to $x'\in X$ and $f_1(x')\leq f_1(x)$. Continue this iterative procedure for every objective function, in descending order of the importance of each objective function.
To implement a heuristic with a lexicographic objective function, there exist different solutions.
- Assign a weight $M_i$ to each objective function $i=1,2,\dots,n$, with $M_1\gg M_2 \gg \dots \gg M_n$.You can than solve $f(x)=M_1f_1(x)+M_2f_2(x)+\dots+M_nf_n(x)$. In other words, you simply combine all objective functions into a single weighted objective function.
An example in the context of a vehicle routing problem: $f_1=$ the total number of vehicles needed, $f_2=$ total driving distance of the vehicles. You could minimize $M_1f_1(x)+f_2(x)$, where $M_1$ is an upper bound on the total driving distance (e.g. the sum of the 2 longest edges out of each customer). Alternatively, if you don't want to mimic an exact lexicographic function, you could simply set $M_i=2^{n-i}$ or $M_i=10^{n-i}$. Note that this kind of objective function has a major disadvantage: many common heuristics, including for instance Simulated Annealing, perform a lot better if the objective function is smooth, i.e. minor changes in the solution result in minor changes in the objective. With this multi-objective approach, a minor change in the solution might incur a big change in the objective function due to the different weights.
- Another approach is to implement the Lexicographic property directly into your heuristic: first search for a solution $x$ which scores best on $f_1$. Next, search for the solution $x'$ which scores best on $f_2$, while only accepting moves to solutions that have the same score on $f_1$ as $x$.
It is likely that this approach will get you stuck in a local optima quickly.
References to other approaches can be found in this slide deck.
