Abstract

In a Green Pickup-and Delivery problem (GPD), green vehicles (e.g., electric or hybrid cars) are used for routing in the problem domain, and these vehicles are particularly constrained with limited fuel capacity, thus shorter traveling range. A refueling infrastructure providing wide-area coverage, meanwhile, has not been fully developed to this end. A recent study reveals that vehicle routing in
essence with green constraints only, is at least weakly NP-hard, motivating us to pursue a deeper understanding of the underlying computational challenge associated with this “green” intractability. In this paper we perform complexity analysis on several GPD subproblems (namely, RINGs), that is, the
problems whose task-graphs are under a ring structure. Using measures of width/length of rings, we delineate clearly two complexity boundaries: one between weakly and strongly NP-complete, and the other between tractable and intractable in general. Our results bring new insights for the research and
development (current and active, but with limited success only to this point) of heuristics or algorithms
for solving GPDs

Article ID: 2022L13

Month: May

Year: 2022

Address: Online

Venue: Canadian Conference on Artificial Intelligence

Publisher: Canadian Artificial Intelligence Association

URL: https://caiac.pubpub.org/pub/smw8hvmf