Scientific Program > Talks by Speaker > Mor Andrea

We consider the traveling salesman problem with release dates where the objective is to minimize the completion time: TSP-rd(time). In the TSP-rd(time) an uncapacitated vehicle is loaded with goods, requested by the customers, that arrive at the depot over time. The arrival time of a product at the depot is called its release date. A single vehicle is available to perform deliveries. Each time the vehicle leaves the depot it can serve only customers whose goods have already arrived. The objective is to serve all customers while minimizing the completion time, i.e. the sum of travelling time and waiting times at the depot. We exhibit some properties, propose a mathematical formulation and describe two heuristic solution algorithms. The two algorithms have common scheme consisting of two main components, a large neighborhood search (LNS) and a local search (LS), iterated until the ending conditions are met. Given a solution, composed of one or more routes to serve all the customers, a LNS is carried out by removing a variable number of nodes from their original routes and reinserting them by either solving a MILP, in the matheuristic algorithm, or greedily, in the heuristic one. A LS is then applied on the obtained solution. Computational results and comparisons are shown on instances derived from Solomon's TSP benchmark instances.