סמינר מחלקתי - המחלקה להנדסת תעשייה

מרצה: אורי יובל

הרצאה:

The Multi-Deopt Vehicle Routing Problem, and Sequential Congestion Games

Abstract:

We discuss two unrelated optimization problems. In the Multi-Depot Vehicle Routing Problem (MDVRP), we are given a complete graph G=(V,E), a distance matrix, and k depots. In typical applications, V represents locations of customers, and the depots are initial locations of k (identical) vehicles. The goal is to find a collection of k cycles such that each vertex is in exactly one cycle, and each cycle contains exactly one depot. We also study the variant in which the depots are not specified, but only their number k is. This problem is known as Multiple-TSP. We design special local-search heuristics for these two versions, and prove that their approximation ratio is 2. To the best of our knowledge, theses are the first local search heuristics for these problems with proved performance guarantees. Joint work with Asaf Levin.

In the Sequential Congestion Games model that we consider, there are n agents, and m identical machines. Each agent j has a job that needs to be processed on any one of the machines, and takes p_j time units; all agents know p­₁,…,p_n. The agents select one of the machines for processing their jobs sequentially, starting with agent 1 and ending with agent n. While choosing a machine, an agent knows the choices made by his predecessors, i.e., the current loads on the machines. Once a machine completes processing all the jobs assigned to it, they are (instantaneously) delivered to their agents. The goal of each customer is to have his job delivered at the earliest possible time. We compute the subgame-perfect solution of such games and compare it to the solution that minimizes the overall makespan of the system. Joint work with Refael Hassin.