We study the problem of optimizing assortment decisions in the presence of product-specific costs when customers choose according to a multinomial logit model. This problem is NP-hard, and approximate solutions methods have been proposed in the literature to obtain both lower and upper bounds in a tractable manner. We propose the first exact solution method for this problem and show that provably optimal assortments of instances with up to 1,000 products can be found, on average, in about 2/10 of a second. In particular, we propose a bounding procedure to enhance an approximation method originally proposed by Feldman and Topaloglu and provide tight lower and upper bounds at a fraction of a second. We show how these bounds can be used to effectively identify an optimal assortment. We also describe how to adapt our approach to handle cardinality or space/resource capacity constraints on the assortment as well as assortment optimization under a mixed-multinomial logit model. In both cases, our solution method provides significant computational boosts compared with exact methods from the literature.

The multitrip vehicle routing problem (MTVRP) is a variant of the capacitated vehicle routing problem where each vehicle can perform a subset of routes, called a vehicle schedule, subject to maximum driving time constraints. Despite its practical importance, the MTVRP has received little attention in the literature. Few heuristics have been proposed, and only an exact algorithm has been presented for a variant of the MTVRP with customer time window constraints and unlimited driving time for each vehicle. We describe two set-partitioning-like formulations of the MTVRP. The first formulation requires the generation of all feasible routes, whereas the second formulation is based on the generation of all feasible schedules. We study valid lower bounds, based on the linear relaxations of both formulations enforced with valid inequalities, that are embedded into an exact solution method. The computational results show that the proposed exact algorithm can solve MTVRP instances taken from the literature, with up to 120 customers.

The traveling salesman problem with time windows (TSPTW) is the problem of finding in a weighted digraph a least-cost tour starting from a selected vertex, visiting each vertex of the graph exactly once according to a given time window, and returning to the starting vertex. This n𝒫-hard problem arises in routing and scheduling applications. This paper introduces a new tour relaxation, called ngL-tour, to compute a valid lower bound on the TSPTW obtained as the cost of a near-optimal dual solution of a problem that seeks a minimum-weight convex combination of nonnecessarily elementary tours. This problem is solved by column generation. The optimal integer TSPTW solution is computed with a dynamic programming algorithm that uses bounding functions based on different tour relaxations and the dual solution obtained. An extensive computational analysis on basically all TSPTW instances (involving up to 233 vertices) from the literature is reported. The results show that the proposed algorithm solves all but one instance and outperforms all exact methods published in the literature so far.