# Mosel Sub Model for the Santa Rideshare Optimization Challenge

File uploaded by oliverbastert@fico.com on Nov 25, 2015
Version 1Show Document

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.