Green Weber Problem
Arsham Atashi
Department of Industrial Engineering, Middle East Technical University

Abstract

The Weber problem corresponds to locating a single facility on the plane so as to minimize the sum of the weighted Euclidean distances between the facility and the customers. Its applications can be exemplified by locating warehouses or facilities for a distribution system in which the demands will be delivered by vehicles directly to the customers. Fuel consumption of the vehicles in such distribution systems results in the emissions of huge amounts of greenhouse gases. In this scope, we introduce an extension of the Weber problem named as the green Weber problem (GWP) that aims to minimize the amount of CO² emitted by the vehicles in the distribution system. In the GWP, the vehicles serving a customer have to arrive at the location of the customer on or before the customer’s time limit. Therefore, in addition to the location of the facility, the speeds of the vehicles are also determined in the GWP. We show that the GWP has a second order cone programming (SOCP) formulation that can be solved in polynomial time. The multi-facility version of this problem, called as the multi-facility green Weber problem (MF-GWP), determines the locations of p facilities on the plane and the speeds of the vehicles serving the customers while minimizing the total CO² emission. We formulate the MF-GWP as a mixed integer second order cone programming (MISOCP) problem. Since this formulation is weak and highly symmetric, only small size instances can be solved to optimality. To be able to solve larger size instances, well-known heuristics developed for the multi-facility Weber problem such as the alternate location-allocation heuristic, transfer follow-up heuristic, and decomposition heuristic are utilized in addition to a newly developed local search approach. The computational results with the MISOCP formulation on small size instances show that breaking the symmetry reduces the solution time and the tighter the time limits of the customers, the lower the solution times we have. For larger size instances, computational experiments are performed to compare different heuristics in terms of solution quality and time. Due to the experiments, the modified versions of transfer heuristic and decomposition heuristic succeed in improving the solution of alternate location allocation heuristic.

Short Bio

Arsham Atashi Khoei is a PhD student in Industrial Engineering Department of Middle East Technical University since February 2015. He received his BSc. and MSc. degrees in 2009 and 2012, from Industrial Engineering in Iran. Currently he is working at Industrial Engineering Department of TED University as a research assistant. His recent research areas include CO² emission concerns in location problems and distribution systems.

Venue

Friday, March 9, 2018 at 4.00 pm in IE03