Decision Optimization

 View Only

Solve a Vehicle Routing Problem (VRP) using CPLEX

  • 1.  Solve a Vehicle Routing Problem (VRP) using CPLEX

    Posted Mon February 26, 2024 12:20 PM

    I am a beginner in CPLEX. I want to solve the VRP problem by using CPLEX. Below I provide a description of the problem. I am very grateful to those who are willing to help. Thank you in advance.

    PROBLEM DESCRIPTION

    A fleet of ships pick up and drop passenger at designated ports. The ships are of different types. They can only refuel in certain ports, called fuel ports. So in a route, the ships must visit at least one fuel port. In a VRP, the fuel ports are similar to depots. There are distance and time constraints of ships in serving a route.

    The objective of this VRP is to minimize the number of transits. Suppose s is the total number of ports in route k, dij is the mile distance from port i to port j and, ck is number of fuel consumption of ship k. Then the total fuel consumption of routes is:

    (1)

    Constraints

    The constraints for the problem are maximum voyage time, maximum mileage of voyage, and port served. The maximum voyage time of ships is 336 hours, determined by the company. Suppose dij is the distance between port i to port j, and vk is the speed of the ship k, then voyage time of ship k from port i to port j is:   (2)

    Route r consists of s port, and then voyage time of ship k in serving the route r is:

    (3)

    If maximum voyage time is T, then:

    (4)

    So that the maximum voyage time of ship k to serve route r is calculated by:

    (5)

    Maximum mileage of voyage is the maximum mileage that a ship can take after refuelling. It is calculated from a fuel port to another fuel port in a route. Suppose maximum fuel tank capacity of ship k is qk. Speed of the ship is vk and power of its engine is pk. The number of engine operated is nk with µ is efficiency of the engine and ƞ is factor constant. Then maximum mileage of ship k is given in (6).

    (6)

    A route must include at least one fuel port.

    (7)

    where,fi are coefficients with the following property:

    (8)

    Each port must be served at least once. For given p, where p is number of port must satisfy the condition

    (9)

    where, ai are coefficients with the following property:

    (10)

    nomenclature

    P       = the index of a set of all ports, P = {1, 2, …, p}

    K       = the index of a set of ships, K = {1, 2, …, k}

    S        =   the index of a set of ports in a route, S = {1, 2, …, s}

    vk       =   speed of ship k

    qk      =   maximum fuel tank capacity of ship k

    pk      =   power of the ship k engine

    nk      =   the number of engine operating on ship k

    ck         =   fuel consumption of ship k

    µ       =   efficiency of engine

    ƞ        =   constant factor

    T       = maximum allowed routing time (commission days)

    ti        =   spent time at port i

    dij      = distance port i to port j; dij is not necessary equals to dji

    ai       =   binary variable denoting that port i is served (1), or otherwise (0)

    fi        =   binary variable denoting that port i to j is a fuel port (1), or otherwise (0)



    ------------------------------
    Nur Iksan
    ------------------------------