To benchmark the performance of a heuristic before it is applied to a more complicated problem that can't easily (or ever) be solved by ILP or MILP.

Dear Thaeer M Sahib,

the Routing Problem (RP) is a typical problem that is "time sensitive". It's a recursive problem. The concept of Linear Programming (IP) was developed mainly to solve economic and non-time-oriented problems. The ILP idea is suitable for solving only a few transport problems where the RP is not the main problem.

The iterative procedures for solving typical RPs are usually based on Richard E. Bellman's Principle of Optimality.

One way of using the Principle of Optimality is called Dynamic Programming (DC). Several methods for solving various RPs are based on the idea of DC - for example in PERT Networks, Communication /Computer Networks, ...

In Chapter "Dynamic Programming (DC)"

https://www.researchgate.net/publication/312033832_Dynamic_Programming

simple examples for the use of DC are shown:

Example 4.41: DC usage in PERT Networks (Pages: 341-344)

Example 4.42: DC use for solving RPs in Communication Networks (Pages: 344-348)

See also:

https://en.wikipedia.org/wiki/Richard_E._Bellman

https://ecal.berkeley.edu/files/ce191/CH05-DynamicProgramming.pdf

https://www.engineeringenotes.com/networking/network-analysis/top-4-problems-on-pert-network-analysis-networking/15725

Best regards

Anatol Badach

Casting a problem using mixed integer-linear programming model does not make the problem easier. The run-times of algorithms for solving MILP are high. Heuristics often provide good solutions quickly.

Dear Thaeer M Sahib

Adding to the good answers already given: It isn't accurate to say that MIP (Mixed-Integer Programming) hasn't been applied to routing problems. A good place to start is searching for optimal solution methods for VRPTW (the Vehicle Routing Problem with Time Windows). Nevertheless, heuristics remain the most widely-used approach. In my experience, this is due to two main reasons:

First is the reason that has already been mentioned in previous answers, which is the problem size when expressed as a linear program. In a typical formulation, if you have n customers to serve and v vehicles, you need at least n*n*v variables. However, there is often need to serve thousands of customers with hundreds of vehicles. This doesn't mean MIP can't be used: For example, some authors use problem decomposition - specifically column generation - plus introduction of auxiliary constraints that accelerate the solver algorithms and reduce the integrality gap.

Second, in practice each problem has its own specific constraints and objective function, and even for the same application (say, field service scheduling), the same organization may need to change the constraints and objective function. Using MIP, especially in the more complex form involving problem decomposition and auxiliary constraints, would then require a deep re-analysis of the problem formulation and the solution approach. For example, consider the common situation where some of the tasks require multiple steps, in a certain order, and these steps may or may not require completion on the same day, or performance by the same vehicle. Heuristic approaches are typically easier to adapt to such changes.

I hope this helps.

Best regards

Israel Beniaminy

I would say that this forum (RG) is the only forum on science that have a very strong tendency to talk about metaheuristics; the fora that I mainly take part in are mathematical optimisation fora, which exclude to a large extent discussions about metaheuristics, and for a very good reason: if you want to find an optimum then a metaheuristic will never be enough.

And just because one has to solve a MIP, it does NOT imply that every such problem is very hard - there are easier ones and tougher ones, and by and large most of the practical problems arising in academia and in most enterprises are not too hard to cope in this day and age!

Hence: there is seldom a need to resort to inferior tools, such as metaheuristics.

And: perhaps the must important for the owner of the problem, as well as the one who is asked to code a solver for the problem: the owner of the problem will ask if the output is optimal, and if you are the one who has done a bad job, such as only implemented a metaheuristic - you will be thrown out!

Thaeer M Sahib : Your question is ambiguous: "routing" can refer, e.g., to vehicle routing or routing of messages/packets in telecommunications networks. Please can you clarify? Thanks.

I'm quite sure that it is the vehicle routing type.

The MILP or even LP might be intractable for realistic size problems. In that case, you have to resort to heuristic methods. Also, if the problem has to be solved in real-time, to modify the routes as the vehicles are moving, MILP will likely not be a good option. A good enough solution might be preferable in other scenarios, especially if the parameter values are not reliably estimated.

Some useful contextualization for the "simplest" variant of the vehicle routing problem (the CVRP):

• The Christofides, Mingozzi, and Toth [CMT] vehicle routing instances with up to 200 clients have been released in 1979, and it took around 35 years of research and progress on exact methods to solve them optimally. In particular, simple MILP formulation for the CVRP (e.g., two-index vehicle flow formulation) can only solve some problems with a few dozens of clients.

• For the newer Uchoa et al. [X] instances with 100 to 1000 clients, there are monetary prizes for anyone able to consistently solve them to optimality (http://vrp.atd-lab.inf.puc-rio.br/index.php/en/cvrp-challenge). So far, these prizes remain unclaimed, and many instances with as few as 300 clients are unsolved.

• Practical applications often involve >5,000 clients (!!!) and *many* complicating constraints, additional decisions, and objectives called "attributes". Application cases with over 50,000 stops/clients are also quite common in courier delivery and refuse collection. Opting for an optimal solution through MILP in these situations is a guaranteed failure, and it usually reflects a lack of practical experience in the field. Even good lower bounds can be hard to get when problem size grows.

Vehicle Routing Problem is not a simple problem, it is an entire area of research that includes many extensions of it that make it complicated. Practical applications have time and capacity constraints, hundreds of customers, etc. that make the problem way more complicated to solve to optimality. To complicate the matters further, most practical applications have dynamic aspects, i.e. the problem changes and it has to be reoptimized on the fly. Heuristics have to be used.

Dear Prof. Thibaut Vidal ,

I have read some research that implement hybrid methods such as branch-and-cut-and-price for VRP, but they only show some small size problems. I wonder what is the maximum problem size that such a hybrid approach can deal with?

Thank you

Tan Pham : I'm not sure I would class branch-cut-and-price as a "hybrid" method. It is the best-performing exact method at present. It can cope with instances with up to 200 customers or so, but this depends heavily on the nature of the side-constraints. (For example, VRPs with very narrow time windows tend to be easier than ones with wide windows.)

This paper should give you an idea of the current limits:

Pessoa, A., Sadykov, R., Uchoa, E., & Vanderbeck, F. (2020) A generic exact solver for vehicle routing and related problems. Mathematical Programming, 183, 483-523.

Thank you very much for your answer, Prof. Adam N. Letchford

Hello Tan Pham

The response of Adam N. Letchford is great. Another characteristic that heavily impacts the ability to solve vehicle routing problem instances with branch-cut-price (BPC) is the average number of stops in the routes. Data sets that have few stops per route (e.g., up to 5) are much easier to solve to optimality. In contrast, data sets with over 20 stops per route are very tough for BPC, in that case, classic branch-and-cut may actually perform better. You can see a list of open and closed instances on this webpage (see the Uchoa et al. (2014) tab):

http://vrp.atd-lab.inf.puc-rio.br/index.php/en/

A problem being solved is a "model" of a real system.

These real system models can be rather complex.

Some real system relationships cannot be described by an equation, and logic may be necessary.

Some real system relationships may require millions of equations.

A) So, one can limit the model complexity and solve exactly.

B) Or, one can increase the model complexity and solve approximately.

An organization may decide that they want to recognize a high level of system complexity.

They may have the data, people, technology, and commitment to follow this path.

To say there is seldom a need to solve approximately depends on one's perspective.

At some point the conversation returns to A and B.

We always are concerned about the quality and efficiency of the solutions from heuristics; therefore, testing on problems with an exact solution for new algorithms is a good practice.