0
$\begingroup$

How to formulate the following problem?

The salesman gains a profit $p_{i}$ when visiting a city i, trip between city i and city j costs $c_{ij}$ and takes $t_{ij}$ time. The trip must not exceed a time limit T. The difference between profit and costs must be maximized.

I've formulated this problem as follows:

maximize $\sum _{i=1}^{n} \sum _{j=1}^{n}p_{ij}x_{ij}- \sum _{i=1}^{n} \sum _{j=1}^{n}c_{ij}x_{ij}$

can i formulate trip time as $\sum _{i=1}^{n} \sum _{j=1}^{n}t_{ij}x_{ij}$ and add the constraint $\sum _{i=1}^{n} \sum _{j=1}^{n}t_{ij}x_{ij} \leqslant T$?

I've read also about the Time Dependent TSP (TDTSP), but i'm not sure it's my case...

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ You can formulate this in whatever way you want, as long as the formulation captures your problem. $\endgroup$ – Yuval Filmus Apr 22 at 2:48
  • $\begingroup$ If you leave the condition that all cities must be visited, the sum of p_i is irrelevant. You might create a different problem where not all cities need be visited. $\endgroup$ – gnasher729 Apr 22 at 19:09

Your Answer

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

Browse other questions tagged or ask your own question.