Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Travelling Salesman Shipping Depreciating Items to Different Markets

What would be a good heuristic to use to solve the following challenge?

Quality Blimps Inc. is looking to expand their sales to other cities (N), so they hired you as a salesman to fly to other cities to sell blimps. Blimps can be expensive to travel with, so you will need to determine how many blimps to take along with you on each trip and when to return to headquarters to get more. Quality Blimps has an unlimited supply of blimps.

You will be able to sell only one blimp in each city you visit, but you do not need to visit every city, since some have expensive travel costs. Each city has an initial price that blimps sell for, but this goes down by a certain percentage as more blimps are sold (and the novelty wears off). Find a good route that will maximize profits.

https://www.hackerrank.com/codesprint4/challenges/tbsp

This challenge is similar to the standard Travelling Salesman Problem, but with some extra twists: The salesman needs to track both his own travel costs and the blimps'. Each city has different prices which blimps sell for, but these prices go down over his journey. What would be a fast algorithm (i.e. n log n ) to use to maximize profit?

The prices of transporting the items in a way makes the TSP simpler. If the salesman is in city A and wants to go to B, he can compare The costs of going directly to B vs. costs of going back to Headquarters first to pick up more blimps. I.e. is it cheaper to take an extra blimp to B via A or to go back in-between. This check will create a series of looped trips, which the salesman could then go through in order of highest revenue. But what would be a good way to determine these loops in the first place?

like image 698
Ari Avatar asked Feb 04 '13 16:02

Ari


People also ask

What is the best strategy to solve the traveling salesperson problem?

To solve the TSP using the Brute-Force approach, you must calculate the total number of routes and then draw and list all the possible routes. Calculate the distance of each route and then choose the shortest one—this is the optimal solution. This method breaks a problem to be solved into several sub-problems.

What are the conditions for travelling salesman problem?

The traveling salesman problem (TSP) is a classical problem of combinatorial optimization. In the TSP, one is given a n × n distance matrix C = ( c i j ) and looks for a cyclic permutation of the set { 1 , 2 , … , n } that minimizes the function c ( τ ) = ∑ i = 1 n c i τ ( i ) .

What is travelling salesman problem explain with example?

Travelling Salesman Problem (TSP) : Given a set of cities and distances between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.

Which algorithm is used for travelling salesman problem?

The water flow-like algorithm (WFA) is a relatively new metaheuristic that performs well on the object grouping problem encountered in combinatorial optimization. This paper presents a WFA for solving the travelling salesman problem (TSP) as a graph-based problem.


2 Answers

This is a search problem. Assuming the network is larger than can be solved by brute force, the best algorithm would be Monte Carlo Tree Search.

like image 132
Tyler Durden Avatar answered Nov 15 '22 03:11

Tyler Durden


Algorithms for such problems are usually of the "run the solution lots of times, choose the best one" kind. Also, to choose what solution to try next, use results of previous iterations.

As for a specific algorithm, try backtracking with pruning, simulated annealing, tabu search, genetic algorithms, neural networks (in order of what I find relevant). Also, the monte carlo tree search idea proposed by Tyler Durden looks pretty cool.

like image 30
maniek Avatar answered Nov 15 '22 05:11

maniek