Solving the Time Dependent Minimum Tour Duration and Delivery Man Problems with Dynamic Discretization Discovery

In this paper, we present exact methods for solving the Time Dependent Minimum Duration Problem (TDMTDP) and the Time Dependent Delivery Man Problem (TD-DMP). Both methods are based on a Dynamic Discretization Discovery (DDD) approach for solving the Time Dependent Traveling Salesman Problem with Time Windows (TD-TSPTW). Unlike the TD-TSPTW, the problems we consider in … Read more

Interval-based Dynamic Discretization Discovery for Solving the Continuous-Time Service Network Design Problem

We introduce an effective and efficient iterative algorithm for solving the Continuous-Time Service Network Design Problem. The algorithm achieves its efficiency by carefully and dynamically refining partially time-expanded network models so that only a small number of small integer programs, defined over these networks, need to be solved. An extensive computational study shows that the … Read more

A two-stage stochastic optimization model for the bike-sharing allocation and rebalancing problem

The Bike-sharing allocation and rebalancing problem is the problem of determining the initial daily allocation of bikes to stations in a bike-sharing system composed of one depot and multiple capacitated stations, in which bikes can be rebalanced at a point in time during the day. Due to the uncertain demand in each station, we propose … Read more

Solving Time Dependent Traveling Salesman Problems with Time Windows

We present a new solution approach for the Time Dependent Traveling Salesman Prob- lem with Time Windows. This problem considers a salesman who departs from his home, has to visit a number of cities within a pre-determined period of time, and then returns home. The problem allows for travel times that can depend on the … Read more

The Continuous Time Service Network Design Problem

Consolidation carriers transport shipments that are small relative to trailer capacity. To be cost-effective, the carrier must consolidate shipments, which requires coordinating their paths in both space and time, i.e., the carrier must solve a Service Network Design problem. Most service network design models rely on discretization of time, i.e., instead of determining the exact … Read more

Branch-and-Price Guided Search for Integer Programs with an Application to the Multicommodity Fixed Charge Network Flow Problem

We develop an exact algorithm for integer programs that uses restrictions of the problem to produce high-quality solutions quickly. Column generation is used both for generating these problem restrictions and for producing bounds on the value of the optimal solution. The performance of the algorithm is greatly enhanced by using structure, such as arises in … Read more

Improved Load Plan Design Through Integer Programming Based Local Search

We present integer programming models of the service network design problem faced by less-than-truckload (LTL) freight transportation carriers, and a solution approach for the large-scale instances that result in practical applications. To accurately represent freight consolidation opportunities, the models use a fine discretization of time. Furthermore, the models simultaneously route freight and empty trailers, and … Read more