0
$\begingroup$

Suppose I have some locations where goods are to be delivered in multiple time slots(like 7-10 am , 10 am-1 pm, time slots are continuous). All the locations are connected with each other(completely connected graph).

1.) Firstly orders of first slot are to be delivered and then only orders of other slots can be delivered.So, the last point of most optimal first slot sub-tour might not be the most optimal for the overall distance minimization. We might need to go from that last point to some other point of first slot and then from there on go to locations of slot2.

2.) Minimize distance

3.) Trip starts from a depot and ends at the depot( So sequence is something like depot -> Slot 1 orders -> Slot 2 orders -> .......... -> depot , where slot1 is 7-10 am , slot2 is 10 am - 1 pm, slot3 is 1 pm - 4 pm......).

My question is how can this problem be tackled with simulated annealing. like how to fix the starting and end points(as depot) and how to set annealing schedule for such problem.

$\endgroup$
  • $\begingroup$ Could you write down the question more formally? It is unclear to me how many vehicles you have, whether there is a starting point for each vehicle, if some locations need to be visited multiple times or not and if the graph contains time distances. $\endgroup$ – Albert Hendriks Aug 21 '16 at 9:09
1
$\begingroup$

To solve a combinatorial optimisation problem such as this by a method such as Simulated Annealing, you need 3 basic ingredients:

  1. A representation for a 'Candidate Solution'. For vehicle routing, this is typically a permutation of the depots, i.e. a list of depots in the order to be visited.

  2. A measure of the quality of a candidate solution. Various methods exist for penalising solutions with deliveries outside their time windows or fail to meet other constraints.

  3. One or more 'perturbation operators' for transforming a candidate solution into another (hopefully better) one. For example, swapping two randomly-chosen depots in the permutation is one of the simplest approaches, but of course more informed operators as possible.

Given these three, it's then possible to plug your problem into a range of metaheuristics, such as iterated local search, Tabu search, various Evolutionary Algorithms or Tabu search.

As regards annealing schedule, there's a range of literate on choosing parameters, but one simple option is to obtain initial and final temperatures from the statistics of a sequence of random perturbations, then experiment with the choice of cooling rate in a geometric annealing schedule.

The excellent (and freely-available) book "Essentials of Metaheuristics" offers a more detailed background on the above and some guidelines for what techniques to apply in what circumstances.

$\endgroup$
  • $\begingroup$ Hi @NietzscheanAI , this is useful information, but I also wanted to ask ,is it feasible to first find optimal path in slot 1 by SA. and then solve slot 2 optimal path by another SA(by considering the last node of slot1 optimal sequence(by SA 1) as the depot for slot2 ) . Basically the problem is'nt exactly VRP, but TSP with time slots( just the orders of first slot are to be ordered before slot2 orders). So we don't need to put constraints on anything. we have to just minimize the total distance(such that all slot1 orders are delivered first and then we proceed to slot2 orders). $\endgroup$ – Raman Sharma Aug 22 '16 at 10:32
  • $\begingroup$ It sounds like, before trying SA (which is known as perturbative method, since it moves in the space of complete tours), you might want to look at a constructive heuristic, which successively adds to a partial tour. The most 'cheap and cheerful' constructive heuristic for the TSP is en.wikipedia.org/wiki/Nearest_neighbour_algorithm, but other options include en.wikipedia.org/wiki/Ant_colony_optimization_algorithms. $\endgroup$ – NietzscheanAI Aug 22 '16 at 12:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.