2
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Are you using Gurobi/CPLEX? $\endgroup$ Sep 29 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.M
    Sep 29 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
    Sep 29 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.M
    Sep 29 at 21:41
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.