We consider the facility location problem of installing a refueling and recharging infrastructure for vehicles with a strongly limited driving range. For this purpose, a novel problem formulation is introduced that is based on an analogy to the well-known duality relationship of Max Flow and Min Cut. In order to optimally solve this problem, a decomposition-based Branch&Cut approach is developed that iteratively generates violated inequalities and so-called zero-half-cuts as specific cutting planes. A comprehensive computational study on two real-world road networks reveals that this considerable tightening of partial problems in each node enables an efficient enumeration process whereby even large scale instances are solved to optimality for the first time.

Introduction

This study deals with the planning of a refueling and recharging infrastructure for vehicles with a strongly limited driving range. While such networks exist for vehicles with traditional fuel combustion engines that have a substantially larger driving range, comparable infrastructures are still lacking in most countries for electric or alternative fuel vehicles. Hence, substantial efforts are being made to reduce these deficits and to establish these vehicles in the market (Upchurch, Kuby, & Lim, 2009). Primarily, these efforts relate to the establishment of a competitive refueling and recharging infrastructure on a nationwide basis (Chung & Kwon, 2015; Lim & Kuby, 2010). From this perspective, the present study considers a specific facility location problem that pursues a maximal coverage of the expected travel demands of potential customers by opening a limited number of refueling or recharging stations (henceforth referred to as stations) in the network. The quality of a found network structure is measured by the attained fulfillment degree of the total demand of all customers, in what follows denoted as the service level. Alternatively, one may seek to develop a network structure that attains a predetermined service level with a minimum number of opened stations. The model defines the demand to be covered by OD-pairs, i.e., combinations of an origin and a destination of travel, weighted by an estimated number of corresponding customers.