none
VRP - Vehicle Routing Problem RRS feed

  • Question

  • Hello there, I'm new to this community I was wondering if any of you has a VRP code that uses Solver.Foundation.In alternative, I have found Airline Allocation which seems to solve a similar problem. Would you please help me decoding it?

    // Copyright © Microsoft Corporation.  All Rights Reserved.
    // This code released under the terms of the 
    // Microsoft Public License (MS-PL, http://opensource.org/licenses/ms-pl.html.)
    
    ///Problem Description
    ///----------------------------------------------------------------------------------------------------------
    ///In this model a fleet of airplanes is to be assigned to a differnt routes.
    ///The demands along the routes are stochastic and clients may be bumped if demand is greater than allocation,
    ///bumped clients cost money.
    ///The objective is to minimize the the operational cost
    ///Sample is taken from A.R. Ferguson and G.B. Dantzig, "The allocation of aircraft to routes—an example 
    ///of linear programming under uncertain demand", Management Science 3 (1956) 45–73
    ///----------------------------------------------------------------------------------------------------------
    
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using Microsoft.SolverFoundation.Services;
    using Microsoft.SolverFoundation.Common;
    using System.IO;
    
    namespace AirlineAllocation
    {
        class AirlineAllocationModel
        {
            private AircraftFleetSize[] _aircraftFleetSize;
            private CostOfOneWayTicket[] _costOfOneWayTicket;
            private AllocationData[] _allocationData;
            private DemandData[] _demandData;
    
            public void BuildModelAndSolve()
            {
                SolverContext context = SolverContext.GetContext();
                Model model = context.CreateModel();
    
                Set aircraftKindSet = new Set(Domain.Any, "AircraftKindSet");
                Set routesSet = new Set(Domain.Any, "RoutesSet");
    
                Parameter capacity = new Parameter(Domain.IntegerNonnegative, "Capacity", routesSet, aircraftKindSet);
                Parameter flightCost = new Parameter(Domain.RealNonnegative, "FlightCost", routesSet, aircraftKindSet);
                Parameter aircraftFleetSize = new Parameter(Domain.IntegerNonnegative, "AircraftFleetSize", aircraftKindSet);
                Parameter costOfOneWayTicket = new Parameter(Domain.RealNonnegative, "CostOfOneWayTicket", routesSet);
                ScenariosParameter demand = new ScenariosParameter("Demand", routesSet);
    
                model.AddParameters(capacity, flightCost, aircraftFleetSize, costOfOneWayTicket);
                model.AddParameter(demand);
    
                // Setting the data for the parameters
                capacity.SetBinding(_allocationData, "Capacity", "Route", "Aircraft");
                flightCost.SetBinding(_allocationData, "Cost", "Route", "Aircraft");
                aircraftFleetSize.SetBinding(_aircraftFleetSize, "Size", "Aircraft");
                costOfOneWayTicket.SetBinding(_costOfOneWayTicket, "Cost", "Route");
                demand.SetBinding(_demandData, "Probability", "Demand", "Route");
    
                // We need to decide how many plains to allocate for each route
                Decision allocation = new Decision(Domain.RealNonnegative, "Allocation", routesSet, aircraftKindSet );
                model.AddDecision(allocation);
    
                // In order to meet the demand we nay need to bump some clients which will cost as money
                RecourseDecision bumped = new RecourseDecision(Domain.RealNonnegative, "Bumped", routesSet);
                // Routes with a lower demand than allocation will have some empty seats 
                RecourseDecision emptySeats = new RecourseDecision(Domain.RealNonnegative, "EmptySeats", routesSet);
    
                model.AddDecisions(emptySeats, bumped);
    
                model.AddConstraint("FleetUsed", 
                Model.ForEach(aircraftKindSet, aircraft => Model.Sum(Model.ForEach(routesSet, route => allocation[route, aircraft])) <= aircraftFleetSize[aircraft]));
    
                model.AddConstraint("DemandSatisfied",
                Model.ForEach(routesSet, route => Model.Sum(Model.ForEach(aircraftKindSet, aircraft => capacity[route, aircraft] * allocation[route, aircraft]))- emptySeats[route] + bumped[route] == demand[route]));
    
                model.AddGoal("Cost", GoalKind.Minimize,
                Model.Sum(Model.ForEach(aircraftKindSet, aircraft => Model.ForEach(routesSet, route => flightCost[route, aircraft] * allocation[route, aircraft]))) +
                Model.Sum(Model.ForEach(routesSet, route => costOfOneWayTicket[route] * bumped[route])));
    
                Console.WriteLine("Solving the airline allocation...");
    
                Solution solution = context.Solve();
                Report report = solution.GetReport();
                Console.WriteLine(report.ToString());
                Console.ReadLine();
    
            }
        
            public void InitData()
            {
                //This part sets the fleet size
                _aircraftFleetSize = new AircraftFleetSize[] 
                {
                    new AircraftFleetSize("aircraft1", 10),
                    new AircraftFleetSize("aircraft2", 19),
                    new AircraftFleetSize("aircraft3", 25),
                    new AircraftFleetSize("aircraft4", 15)
                };
    
                //This part sets the cost of one way tickets
                _costOfOneWayTicket = new CostOfOneWayTicket[] 
                {
                    new CostOfOneWayTicket("route1", 13),
                    new CostOfOneWayTicket("route2", 13),
                    new CostOfOneWayTicket("route3", 7),
                    new CostOfOneWayTicket("route4", 7),
                    new CostOfOneWayTicket("route5", 1)
                };
    
                //This is the part that control the allocatuon of route, aircraft, capacity, cost
                _allocationData = new AllocationData[] 
                {
                    new AllocationData("route1", "aircraft1", 16, 18),
                    new AllocationData("route2", "aircraft1", 15, 21),
                    new AllocationData("route3", "aircraft1", 28, 18),
                    new AllocationData("route4", "aircraft1", 23, 16),
                    new AllocationData("route5", "aircraft1", 81, 10),
                    new AllocationData("route1", "aircraft2", 0, 0),
                    new AllocationData("route2", "aircraft2", 10, 15),
                    new AllocationData("route3", "aircraft2", 14, 16),
                    new AllocationData("route4", "aircraft2", 15, 14),
                    new AllocationData("route5", "aircraft2", 57, 9),
                    new AllocationData("route1", "aircraft3", 0, 0),
                    new AllocationData("route2", "aircraft3", 5, 10),
                    new AllocationData("route3", "aircraft3", 0, 0),
                    new AllocationData("route4", "aircraft3", 7, 9),
                    new AllocationData("route5", "aircraft3", 29, 6),
                    new AllocationData("route1", "aircraft4", 9, 17),
                    new AllocationData("route2", "aircraft4", 11, 16),
                    new AllocationData("route3", "aircraft4", 22, 17),
                    new AllocationData("route4", "aircraft4", 17, 15),
                    new AllocationData("route5", "aircraft4", 55, 10)
                };
    
                //This is the part that control the route, the probability, and the demand
                _demandData = new DemandData[] 
                {
                    new DemandData("route1", 0.04, 175), new DemandData("route1", 0.04, 185), new DemandData("route1", 0.04, 195), 
                    new DemandData("route1", 0.04, 200), new DemandData("route1", 0.04, 210), new DemandData("route1", 0.05, 220), 
                    new DemandData("route1", 0.35, 250), new DemandData("route1", 0.1, 270), new DemandData("route1", 0.05, 280), 
                    new DemandData("route1", 0.05, 290), new DemandData("route1", 0.04, 300), new DemandData("route1", 0.04, 305), 
                    new DemandData("route1", 0.04, 310), new DemandData("route1", 0.04, 312), new DemandData("route1", 0.04, 314), 
    
                    new DemandData("route2", 0.05, 40), new DemandData("route2", 0.05, 45), new DemandData("route2", 0.05, 50), 
                    new DemandData("route2", 0.05, 55), new DemandData("route2", 0.1, 134), new DemandData("route2", 0.1, 138), 
                    new DemandData("route2", 0.1, 142), new DemandData("route2", 0.1, 146), new DemandData("route2", 0.1, 150), 
                    new DemandData("route2", 0.1, 154), new DemandData("route2", 0.1, 158), new DemandData("route2", 0.05, 160), 
                    new DemandData("route2", 0.05, 162),  
    
                    new DemandData("route3", 0.05, 138), new DemandData("route3", 0.05, 140), new DemandData("route3", 0.02, 156), 
                    new DemandData("route3", 0.04, 158), new DemandData("route3", 0.1, 160), new DemandData("route3", 0.02, 162), 
                    new DemandData("route3", 0.02, 164), new DemandData("route3", 0.1, 170), new DemandData("route3", 0.1, 175), 
                    new DemandData("route3", 0.1, 180), new DemandData("route3", 0.1, 185), new DemandData("route3", 0.06, 188), 
                    new DemandData("route3", 0.06, 200), new DemandData("route3", 0.04, 205), new DemandData("route3", 0.04, 210), 
                    new DemandData("route3", 0.07, 220), new DemandData("route3", 0.03, 222), 
    
                    new DemandData("route4", 0.1, 5), new DemandData("route4", 0.1, 10), new DemandData("route4", 0.05, 30), 
                    new DemandData("route4", 0.05, 37), new DemandData("route4", 0.05, 50), new DemandData("route4", 0.05, 57), 
                    new DemandData("route4", 0.15, 80), new DemandData("route4", 0.15, 85), new DemandData("route4", 0.1, 100), 
                    new DemandData("route4", 0.1, 110), new DemandData("route4", 0.02, 300), new DemandData("route4", 0.02, 320), 
                    new DemandData("route4", 0.02, 340), new DemandData("route4", 0.02, 360), new DemandData("route4", 0.02, 380), 
    
                    new DemandData("route5", 0.03, 570), new DemandData("route5", 0.04, 580), new DemandData("route5", 0.03, 590), 
                    new DemandData("route5", 0.05, 600), new DemandData("route5", 0.05, 602), new DemandData("route5", 0.1, 604), 
                    new DemandData("route5", 0.1, 606), new DemandData("route5", 0.2, 610), new DemandData("route5", 0.1, 612), 
                    new DemandData("route5", 0.1, 614), new DemandData("route5", 0.1, 616), new DemandData("route5", 0.05, 618), 
                    new DemandData("route5", 0.05, 620) 
                };
        }
    
        private class AircraftFleetSize
            {
                public string Aircraft { get; set; }
                public int Size { get; set; }
                public AircraftFleetSize(string aircraft, int size)
                {
                    Aircraft = aircraft;
                    Size = size;
                }
            }
    
        private class CostOfOneWayTicket
            {
                public string Route { get; set; }
                public double Cost { get; set; }
                public CostOfOneWayTicket(string route, double cost)
                {
                    Route = route;
                    Cost = cost;
                }
            }
    
        private class AllocationData
            {
                public string Aircraft { get; set; }
                public string Route { get; set; }
                public int Capacity { get; set; }
                public double Cost { get; set; }
                public AllocationData(string route, string aircraft, int capacity, double cost)
                {
                    Aircraft = aircraft;
                    Route = route;
                    Capacity = capacity;
                    Cost = cost;
                }
            }
    
        private class DemandData
            {
                public string Route { get; set; }
                public double Probability { get; set; }
                public int Demand { get; set; }
                public DemandData(string route, double probability, int demand)
                {
                    Route = route;
                    Probability = probability;
                    Demand = demand;
                }
            }
      }
    
      class AirlineAllocation
        {
            static void Main(string[] args)
            {
                AirlineAllocationModel airlineAllocationModel = new AirlineAllocationModel();
                airlineAllocationModel.InitData();
                airlineAllocationModel.BuildModelAndSolve();
            }
        }
    }
    

    Any help is greatly appreciate it!

    Thanks a lot for your help

    Francesco

    Monday, October 24, 2016 6:43 PM