There is a transportation problem with via points and bandwidth limitations. In addition, there is a transport park. In the task it is necessary to find the optimal solution for the cost of transportation, but this decision will depend not only on the length of the route, but also on the number and type of vehicles selected.

I do not see any other solution than to sort through possible combinations of transport and solve the transportation problem for this combination, because the goal is to find the optimal solution, the quasi-optimal will not work.

Since, with an increase in quantity or diversity, the task becomes unsolvable in the available time, the question is: is it possible to accelerate this matter? What tools / methods can be applied here? Is it possible to tie a map to reduce or apache spark?

ps When solving, it is possible to use a large number of PCs.

  • Exact solution of NP-complete problems by exhaustive search means searching O (2 ** N) variants ... Maybe you think about approximate solutions? - Vasyl Kolomiets
  • @VasylKolomiets Approximate solutions - this is not exactly what we would like, because theoretically, it would be suggested to use not 1 pc, but in general, a network, theoretically, not a small one, to solve this problem. Well, the available time also meant not a second / minute, a couple of weeks would also be nothing =) - Alexander Berlusconi
  • Writing the fastest possible native code is definitely a solution. It is unlikely that something will be faster than him ;-) - Vladimir Martyanov
  • Found Apache Ignite. I’m not completely sure yet, but apparently this is what will help me accomplish a distributed computation. Maybe someone in the know this thing? - Alexander Berlusconi
  • @AlexanderBerlusconi distributed computing can be implemented with map-redus from Hadoop and with Spark. you need to determine the sequence of processing the source data and the parts that can be parallelized, and then - a clean implementation using the API - Alex Chermenin

0