Giter VIP home page Giter VIP logo

milp-pap's Introduction

MILP PAP

UTA PAP is a Mixed Integer Linear Program (MILP) designed to solve the Position Allocation Problem (PAP) for the a general battery electric bus (BEB) system. The position allocation problem is a rectangle packing problem where the x-axis is defined as time and the y-axis is the set of queues for each charger. Given a sequence of bus visits, initial charges, and types of charger, the program will estimate BEB discharges and determine and optimal scheduling for the given routes.

The data ouput of this program is used as an input in the associated MILP PAP paper.

About The Program

This program utilizes the GNU linear programming kit (GLPK) to solve the MILP. The particualar python interface into the GLPK is pyGLPK. Another proprietary solver implemenation is available via Gurobi to solve the MILP. If you wish to use Gurobi, you will need to have a valid license installed. Gurobi and GLPK will be installed as dependencies when make setup is run. By default GLPK will be used as it is open source project and more accessible.

Running the Program

To run, go into source code and type make setup which will set up a python virtual environment and install the dependencies. Type make run to execute the program.

Configuring The Program

All the configuration available to the user can be found in src/config. In that directory the user will find two files:

  • general.yaml
  • schedule.yaml

general.yaml, as the name suggests, contains general configuration for the way the program behaves. This includes items such as:

VariableDefault ValueDescription
plot0Enable/Disable plotting
time_limit21600Solver time limit
schedule_type'csv'Type of bus schedule to use
load_from_file0Load previous results
run_prev0Load previous input parameters and solve
verbose0Verbose output

schedule.yaml conains configuration for the schedule generation specifically. See schedule.yaml for specifics.

NOTE ON RANDOMLY GENERATED SCENARIOS

Due to the randomness of the generated schedule, there here is a chance that the scenario generated is not feasible (although not very likely). There are two YAML files: src/schedule/generate/schedule.yaml where you can enable the run_prev variable which will use the previous generated scenario, but resolve the problem. This is to allow you to change the constraints but keep the same scenario such that you can see the effects of the constraints.

Running Testing

Testing can be conducted by simply typing make test. Once that has been run, the entire of testing suit will be run

milp-pap's People

Contributors

alexb7711 avatar

Stargazers

 avatar

Watchers

 avatar

milp-pap's Issues

Update csvLoader to use member variables instead of static

BOD and EOD will not change if the time horizon is update in the YAML file. This in naughty naughty.

##===============================================================================
# STATIC
BOD = 0.0                                                                       # Beginning of working day
EOD = 24.0                                                                      # End of working day

##===============================================================================
# PUBLIC

##-------------------------------------------------------------------------------
#
def genCSVRoutes(self, path: str="./data/routes.csv"):
    """
    Given the schedule object and a CSV file of routes, load the parameters and
    return a formatted set of routes to optimize over.

    Input:
      - self: schedule scheduler object
      - path: path to CSV file

    Output:
      - But routes loaded from CSV
    """

    routes = __loadCSV(self, path)                                              # Load the route data from CSV

    __bufferAttributes(self, routes)                                            # Load the route attributes into
                                                                                # scheduler object

    visits    = __convertRouteToVisit(routes)                                   # Convert start/end route to
                                                                                # arrival/departure
    discharge = __calcDischarge(self, routes)                                   # Calculate the discharge
    __generateScheduleParams(self, visits, discharge)                            # Generate schedule parameters

    return

Initial indexing is still wrong

When converting routes to visit , the initial index is being set wrong. See sa-pap route_csv_generator.rs:

        arrival_c = r[1]  # Current arrival time # Incorrect
        arrival_n = 0  # Next arrival time
        departure = 0  # Departure time
        tmp_route = []  # Temporary [Arrival, Depart] pair

        ## Determine start/stop index
        (i0, J) = __detStartEndIdx(self, r)

        ## For each start/stop route pair
        for j in range(i0, J, 2):
            ### Update times
            departure = r[j]  # Assign departure time (Incorrect)
            arrival_n = r[j + 1]  # Assign next arrival time (Incorrect) 

Variable reuse issue

in q.append, the q is reused in a weird way. Rename one of them (v or q)

        # Save reservation
        ## If there has been times allotted
        if v >= 0:
          for j in self.cu[v]:
              s = j[0]                                                          # Start of free time
              e = j[1]                                                          # End of free time

              # If the allocated time is in the selected free time
              if s <= u and c <= e:
                q = self.cu[v]
                q.remove(j)                                                     # Remove current free time
                q.append([s, u])                                                # Update charger times
                q.append([c, e])
                break

Tweak Quinn

The Quinn-Modified algorithm does not do a good job with the "full" schedule. Droge, does not like that it produces an infeasible schedule. There are a few options,

  • Make another ignore route list that is a subset of the MILP that Quin can handle
  • Tweak the parameters to make it work better for this specific problem

cleanup

Reread the code and make sure everything is up to snuff. Misc. updates as needed.

Remove misleading comment

This comment in csv_loader.py serves no purpose

##-------------------------------------------------------------------------------
#
def __detStartEndIdx(self, r):
    """
    Determine the starting index for converting routes to visits.

    Example:
    1)
    B  E  B  E  B  E  B  E
    0  1  2  3  4  5  6  7

    The first "visit" it at E = 1 since the BEB is on route from hour 0 to 1.
    Therefore, the first visit is at index 1.

    2)
    B  E  B  E  B  E  B  E
    1  2  3  4  5  6  7  8

    The first visit is at E = 0.0 since we are assuming that B = 1 is the start
    of the first route of the day. Therefore, the starting index needs to be 1.

    Input:
      - self  : Scheduler object
      - r: Vector of bus routes for bus `b`

    Output:
      - (i0, ix): The start/end index to convert routes to visits

    """
    # Variables
    i0 = 0
    ix = len(r)

    return (i0, ix)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.