# Traveling Salesman Problem with profit and time limit as ILP formulation

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

• You can formulate this in whatever way you want, as long as the formulation captures your problem. – Yuval Filmus Apr 22 '19 at 2:48
• 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. – gnasher729 Apr 22 '19 at 19:09