Citation

Malik A, Contreras I, Vidyarthi N. Transp. Sci. 2022; 56(6): 1703-1722.

Copyright

(Copyright © 2022, Institute for Operations Research and the Management Sciences)

DOI

10.1287/trsc.2022.1150

PMID

unavailable

Abstract

Globally, cyclists and pedestrians contribute to 26% of all deaths related to traffic accidents and motorized two- and three-wheeled vehicles contribute to 28%. In Southeast Asia and the Western Pacific, most deaths occurred among two- and three-wheeled motorized bicycle passengers, contributing to 43% and 36% of all deaths related to traffic accidents, respectively [1]. With the public's attention to a low-carbon lifestyle, the electric bike, which takes economy and convenience into consideration, has become an important means of transportation for many people. In China, from 2007 to 2016, more than 30 million electric bikes were added to the road each year, and car ownership increased by an average of 15 million vehicles during the same period. Electric bikes have become one of the main modes of travel for urban residents in China; especially in small and medium-sized cities, the proportion of electric bikes travel is as high as 10%-30% [2]. The traffic safety risk of electric bike is accumulating rapidly. From 2012 to 2016, there were 193,000 road traffic crashes involving electric bikes in China, resulting in 37,700 deaths. Among them, the proportion of active crashes and fatalities of electric bikes was as high as 29.1% and 22.3%, respectively [3]. Electric bike crash is the fastest rising group in the death toll of road traffic crashes.


In this paper, we study a general class of two-level capacitated discrete location problems with concave costs. The concavity arises from the economies of scale in production, inventory, or handling at the facilities and from the consolidation of flows for transportation and transshipment on the links connecting the facilities. Given the discrete nature of the problem, it is naturally formulated as a mixed-integer nonlinear program that uses binary variables for locational decisions and continuous variables for routing flows. We present an alternative formulation that only uses continuous variables and discontinuous functions, resulting in a nonlinear program with a concave objective function. Our main goal is to computationally compare these two modeling approaches under the same solution framework. In particular, we present an exact branch-and-bound algorithm that uses (integer) linear relaxations of the proposed formulations to optimally solve large-scale instances. The algorithm is enhanced with a cost-dependent spatial branching strategy and preprocessing step to improve its convergence. Extensive computational experiments are performed to assess the performance of the exact algorithm. Based on real location data from 3,109 counties in the contiguous United States, we also present a sensitivity analysis to showcase the impact of considering concave costs in location and assignment decisions.

Language: en

Keywords

branch-and-bound; concave costs; hierarchical facility location; mixed-integer nonlinear programming