Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.

 View Only

  • 1.  Subtour Elimination Constraints for Vehicle Routing Problem

    Posted Mon September 27, 2021 08:59 AM
    Hi. I am a newbie in this CPLEX software. Recently i am working on the vehicle routing problem. I do encounter a problem which is regarding the code for subtour elimination constraints. The version of CPLEX that I am using currently is version 20.1.0.0. Can I have some suggestion from the expert here in providing a guidance and references for me. Hope to receive replies from expert in related field of study. Thank you. Here is the mod and dat file for the vehicle routing problem .

    ------------------------------
    Kien Hua Ting
    ------------------------------

    #DecisionOptimization


  • 2.  RE: Subtour Elimination Constraints for Vehicle Routing Problem

    Posted Tue September 28, 2021 11:22 PM
    I am not aware of any pre-existing libraries that you can import into OPL CPLEX IDE.

    However, if you think of migrating to C/C++, you could try to integrate pre-existing C++ code that implements different subtour breaking constraints for the VRP efficiently. For instance, take a look at https://github.com/sassoftware/cvrpsep

    ------------------------------
    CPLEX User
    ------------------------------

    Original Message


  • 3.  RE: Subtour Elimination Constraints for Vehicle Routing Problem

    Posted Thu September 30, 2021 08:55 AM
    Thank you for your suggestion. I appreciate it.

    ------------------------------
    Kien Hua Ting
    ------------------------------

    Original Message


  • 4.  RE: Subtour Elimination Constraints for Vehicle Routing Problem

    Posted Wed September 29, 2021 11:55 AM
    You have the Miller-Tucker-Zemlin constraints in your code, commented out. There is one indexing error related to them in the code. You have to enforce the constraints for all arcs i->j except where i or j is the depot. (Check the indexing of the constraint in the Wikipedia entry.)

    Also, you provide no context for the parameter n. In the MTZ constraints, n is typically the number of nodes (including the depot), but in your data file you have seven nodes but n = 5. This is not automatically a problem, since you have three vehicles, but it does indirectly constrain the model to use all three vehicles, even if it would be more efficient to use only two. That may be intentional on your part; I'm just pointing it out.

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------

    Original Message


  • 5.  RE: Subtour Elimination Constraints for Vehicle Routing Problem

    Posted Thu September 30, 2021 08:57 AM
    Dear Paul Rubin, Thank you for your comments here. i will try to edit my code based on your comments. If i face any other difficulty will seek for your advices and comments. Pleasure to have your precious comments and appreciate it.

    ------------------------------
    Kien Hua Ting
    ------------------------------

    Original Message


Related Content