Matheus Jun Ota

On vehicle routing problems with stochastic demands — Scenario-optimal recourse policies

  • Matheus Jun Ota
  • Ricardo Fukasawa
    • Categories Branch and Cut Algorithms, Stochastic Programming, Transportation Tags , ,

    Two-Stage Vehicle Routing Problems with Stochastic Demands (VRPSDs) form a class of stochastic combinatorial optimization problems where routes are planned in advance, demands are revealed upon vehicle arrival, and recourse actions are triggered whenever capacity is exceeded. Following recent works, we consider VRPSDs where demands are given by an empirical probability distribution of scenarios. Existing … Read more

    On vehicle routing problems with stochastic demands — Generic integer L-shaped formulations

  • Matheus Jun Ota
  • Ricardo Fukasawa
    • Categories Branch and Cut Algorithms, Stochastic Programming, Transportation Tags , , ,

    We study a broad class of vehicle routing problems in which the cost of a route is allowed to be any nonnegative rational value computable in polynomial time in the input size. To address this class, we introduce a unifying framework that generalizes existing integer L-shaped (ILS) formulations developed for vehicle routing problems with stochastic … Read more

    Approximating value functions via corner Benders’ cuts

  • Matheus Jun Ota
  • Ricardo Fukasawa
  • Aleksandr M. Kazachkov
    • Categories Branch and Cut Algorithms, Integer Programming, Stochastic Programming Tags , , , , ,

    We introduce a novel technique to generate Benders’ cuts from a conic relaxation (“corner”) derived from a basis of a higher-dimensional polyhedron that we aim to outer approximate in a lower-dimensional space. To generate facet-defining inequalities for the epigraph associated to this corner, we develop a computationally-efficient algorithm based on a compact reverse polar formulation … Read more

    Hardness of pricing routes for two-stage stochastic vehicle routing problems with scenarios

  • Matheus Jun Ota
  • Ricardo Fukasawa
    • Categories Combinatorial Optimization, Integer Programming, Stochastic Programming Tags , ,

    The vehicle routing problem with stochastic demands (VRPSD) generalizes the classic vehicle routing problem by considering customer demands as random variables. Similarly to other vehicle routing variants, state-of-the-art algorithms for the VRPSD are often based on set-partitioning formulations, which require efficient routines for the associated pricing problems. However, all these set-partitioning-based approaches have strong assumptions … Read more

    A comparison of different approaches for the vehicle routing problem with stochastic demands

  • Matheus Jun Ota
  • Ricardo Fukasawa
    • Categories Branch and Cut Algorithms, Production and Logistics, Stochastic Programming Tags , ,

    The vehicle routing problem with stochastic demands (VRPSD) is a well studied variant of the classic (deterministic) capacitated vehicle routing problem (CVRP) where the customer demands are given by random variables. Two prominent approaches for solving the VRPSD model it either as a chance-constraint program (CC-VRPSD) or as a two-stage stochastic program (2S-VRPSD). In this … Read more