סמינר מחלקתי

Solving routing problems using math heuristics and decomposition methods

Iris Forma-  Ph.D. student

Abstract:

Studies in the field of transportation are expanding due to the growing need of reducing costs and emission of pollution. The development of new modes of transportation in cities and the development of new ways of distribution in the supply chain present new challenging routing problems in the field of operations research. In this talk we present solution methods for two emerging routing problems: a production and distribution problem in supply chains and a repositioning problem in bike sharing systems.

Supply chain management (SCM) involves making decisions on production scheduling, inventory levels of raw materials and finished products, transportation and related aspects, with the objective of minimizing the total cost associated with these activities. While in the past, policies of different functions of the supply chain were managed separately, more recent management practice and studies recognize the advantages of coordinated decision making. We formulate the problem as a Mixed Integer Linear Program (MILP) which integrates decisions of production, inventory, and distribution of products and pick-up of raw materials. We propose and analyze three decomposition methods for solving this problem.

Bike-sharing systems allow people to rent a bicycle at one of many automatic rental stations scattered in the city, use them for a short journey and return them at any station in the city. A crucial factor for the success of a bike sharing system is its ability to meet the fluctuating demand for bicycles at each station. Thus, operators of bike sharing systems are responsible to regularly remove bicycles from some stations and transfer them to other stations, using a dedicated fleet of light trucks. We refer to this activity as repositioning bicycles and formulate it as a MILP for the case of the Static repositioning, i.e., during the night when demand is negligible. Then, we propose a three step math heuristic for solving larger networks than those that can be solved by the MILP formulation.    

This work was performed under the supervision of Prof. Michal Tzur and Dr. Tal Raviv.

ההרצאה תתקיים ביום חמישי 1.1.15, בשעה 12:00 בחדר 206, בנין וולפסון הנדסה, הפקולטה להנדסה, אוניברסיטת תל-אביב.