Mosel Sub Model for the Santa Rideshare Optimization Challenge

File uploaded by Advocate on Nov 25, 2015
Version 1Show Document
  • View in full screen mode

  Capicitated Vehicle Routing Problem (a twist of traveling salesman problem)

  Given a list of gifts, weights, and their locations, deliver them in sleighs with a weight limit

  All sleighs start from north pole, then head to each gift in the order that a user gives, and then head back to north pole

  Sleighs have a base weight

  "Weighted distance" = distance traveled * weights carried for that segment

  Goal: minimize the total weighted distance traveled



  A possible MIP formulation (of problem size O( Locations^2 * sledges * gifts )

    model each gifts path using binary variables, per edge, and per sledge

    model each sledge's path using binary variables

    assign gifts to sledges taking capacity into account

    the gifts' path should be superseded by the sledge's path that is assigned to it

    note: travel time * weight can be priced individually


  The number of sledges is not limited, so we can assume a sledge cannot go back to the Pole to pick up a second round as such

    a round can be served by another sledge  


  This formulation is for demonstration only; due to the combinatoric nature of the formulation, the MIP problem generated will become intractable

    very quickly.