Multi-objective integer nonlinear programming (MOINLP) problems are multi-objective integer programming problems with at least one nonlinear objective function or constraint. To date, MOINLP problem has not been exactly solved. Although traditional ε-constraint method can be used to solve MOINLP problem, the obtained solution may not be Pareto-optimal. To overcome this shortcoming, a basic ε-constraint method (BEM) is proposed to solve MOINLP problem exactly. However, the time complexity of BEM is as high as O((p−1)M2N), where p, M, and N are the numbers of objectives, Pareto-optimal solutions, and feasible solutions, respectively. For this reason, an improved BEM (IBEM) is developed whose time complexity is O(M2N). That is, the time complexity of IBEM for solving MOINLP problem is equal to solving the single-objective one. Finally, to avoid using all the feasible solutions (N) in obtaining each Pareto-optimal solution, three methods to eliminate dominated solutions effectively are used before performing IBEM. The test results illustrate that our method can not only solve MOINLP problem exactly but also has high efficiency.

Motivated by rising concerns regarding global warming and traffic congestion effects, we study the time-dependent green vehicle routing problem with time windows (TDGVRPTW), aiming to minimize carbon emissions. The TDGVRPTW is a variant of the time-dependent vehicle routing problem (TDVRP) in which, in addition to the time window constraints, the minimization of carbon emissions requires determination of the optimal departure times for vehicles, from both the depot and customer location(s). Accordingly, the first exact method based on a branch-cut-and-price (BCP) algorithm is proposed for solving the TDGVRPTW. We introduce the notation of a time-dependent (TD) arc and describe how to identify the nondominated TD arcs in terms of arc departure times. In this way, we reduce infinitely many TD arcs to a finite set of nondominated TD arcs. We design a state-of-the-art BCP algorithm for the TDGVRPTW with labeling and limited memory subset row cuts, together with effective dominance rules for eliminating dominated TD arcs. The exact method is tested on a set of test instances derived from benchmark instances proposed in the literature. The results show the effectiveness of the proposed exact method in solving TDGVRPTW instances involving up to 100 customers. Summary of Contribution: Due to the environmental situation, green vehicle routing problems (GVRPs) aim to consider greenhouse gas emissions reduction, while routing the vehicles, and play a key role in transportation and logistics. Vehicle greenhouse gas emissions strongly depend on the vehicle speeds and traffic conditions which in real life vary continuously over time. To tackle these challenges, we address the time-dependent green vehicle routing problem with time windows (TDGVRPTW) aimed at reducing total carbon emissions under time-dependent travel times and time window constraints. We design an effective exact method for the TDGVRPTW based on a state-of-the-art branch-cut-and-price algorithm. The paper is both of methodological value for researchers and of interest for practitioners. For researchers, the presented algorithm is amenable for various routing constraints and provides a ground for further studies and research. For practitioners, the paper suggests insights on how the carbon emissions change based on different vehicle speed profiles. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research is supported by the National Natural Science Foundation of China [Grants 71831003, 71831006, 72171043, and 71901180] and the Fundamental Research Funds for the Central Universities [Grants N170405005 and N180704015]. Supplemental Material: The electronic companion is available at https://doi.org/10.1287/ijoc.2022.1195 .