50 %
50 %
Information about i DMSS

Published on September 11, 2007

Author: Arundel0

Source: authorstream.com

i-DMSS for Bus Rental in Seoul, Korea:  i-DMSS for Bus Rental in Seoul, Korea Katta G. Murty Dept. IOE, U. of Michigan Ann Arbor, MI-48109-2117, USA e-mail: murty@umich.edu and Woo-Je Kim Dept. of IISE, Seoul National University of Technology 172 Gongneung 2-dong, Nowon-gu, Seoul 139-743, South Korea e-mail: wjkim@snut.ac.kr Work done for Arirang in Seoul, South Korea, which rents buses (with drivers) to groups:  Work done for Arirang in Seoul, South Korea, which rents buses (with drivers) to groups n = up to 100 customer requests daily Each request called job specifies Start location pi Start time t i End location q i _ End time ti Group size D = (dij) is distance data matrix for day Slide3:  Each job involves travel (possibly with stops), driver has to be available to group continuously Two bus types: 45 seat (20 available, for large groups) 15 seat (5 available, for small group) Stationed at two separate depots Company can also borrow buses from other vendors Duration of job = end time - start time Varies from half hour to 20 hours For 75% of jobs, duration is less than five hours Job Number: Serially in increasing order of start Slide4:  Work-sequence: Sequence of jobs handled by a bus in a day Necessary condition for i1, ... ir to be a work- sequence: _ t {s+1} - ts andgt; driving time from qs to p{s+1} for s = 1 to r-1 In this work sequence, the driver of bus from qs to p{s+1} for s = 1 to r called empty load drives _ Duration of this work-sequence: (depends on depot of bus) = tr - t1 + (driving time from depot to p1) + (driving time from qr to depot) Drivers prefer long duration work-sequences (more money). But company has safety limit = 12 hours. But 10% jobs are long andgt; 11 hour duration. They are OK, because they have intermediate stops when driver can rest. Only long duration work-sequences with continuous driving (fatigue causing) problematic Decisions to be made: :  Decisions to be made: Partition trips into work-sequences, each for a bus Allocate buses from two depots, (and outside vendors if necessary) to work- sequences Objectives to Optimize:  Objectives to Optimize min OBJ1 = number of buses to handle jobs = number work-sequences into which jobs partitioned min OBJ2 = total cost of empty load driving Keep OBJ3 = % of long duration work- sequences below 50 as far as possible Representation Using Network G:  Representation Using Network G Each trip a node N = set of nodes Include arc (i, j) if bus can handle trip j after completing trip i A = set of arcs Leave long duration trips as isolated nodes G = (N, A) acyclic network (no directed cycles) Each work-sequence is a chain in G, and each chain (including single node chains) in G can be a work-sequence How to minimize OBJ1?:  How to minimize OBJ1? Can be minimized by finding a min chain cover for nodes of G (i.e., smallest number of chains containing all nodes) This problem transformed into a max bipartite matching problem, can be solved very efficiently How to minimize OBJ2?:  How to minimize OBJ2? OBJ2 = OBJ2.1 + OBJ2.2, OBJ2.1 is cost of empty load drives between consecutive jobs in work- sequence, OBJ2.2 is empty load drives from, to, depot i1 i2 i3 ir .. Slide10:  OBJ2.1 depends only on how jobs portioned into work-sequences for buses OBJ2.2 depends on from which source (depot 1, 2, outside vendor) buses allocated to work-sequences We minimize OBJ2.1, 2.2 in separate stages How to minimize OBJ1, OBJ2.1 simultaneously?:  How to minimize OBJ1, OBJ2.1 simultaneously? Find a min cost max matching in bipartite network, and use it to form work-sequences Can be solved efficiently using assignment algorithm How to Handle OBJ3?:  How to Handle OBJ3? OBJ3 makes problem hard. Even simpler problem of forming work-sequences with no long duration work sequences has been proved hard. Handle OBJ3 heuristically, manually (interactively) Removing longest arc, reapplying algorithm usually reduces % of long duration work sequences, while increasing OBJ1 only slightly Breaking some longest duration multi-trip work-sequences into two of reasonable durations, exchanging trips at beginning or end of some long duration ones to others, always yields good set, to implement How to Minimize OBJ 2.2:  How to Minimize OBJ 2.2 Let WS1,..., WSs be work-sequences in final solution set Let Depot 1, 2, OV (Outside Vendor) be sources of buses Knowing WSt, we can easily calculate value of OBJ 2.2 (cost of driving from source to starting location of first trip + from ending location of last trip back to source) for allocating bus from source to WSt, and model this problem as a 3 x s transportation problem Strategy for the problem:  Strategy for the problem Our strategy is a 2-stage hierarchical process Stage 1: Select work sequences to implement, to min OBJ1, OBJ 2.1 simultaneously, by solving min cost max matching in bipartite network Modify work sequences obtained to satisfy OBJ 3 interactively by heuristic techniques Stage 2: Allocate buses from sources to selected work-sequences to min OBJ 2.2 by solving transportation model How to Handle 2 Bus Sizes?:  How to Handle 2 Bus Sizes? 5 small 15 seat buses On days when more small buses needed, much cheaper to use one of company's large 45 seat buses than renting small bus Use following procedure: 1. Consider only small group jobs. Use algorithm to allocate small buses to these, up to 5 available 2. If any small group jobs unallocated, combine them with set of large group jobs and use algorithm to allocate large buses to this set Results:  Results Previously decisions made manually, took two people Using DSS, solution time reduced to a few man-hours each day OBJ1 reduced by 15% from manual approach OBJ2 reduced by 10% from manual approach

Add a comment

Related presentations

Related pages

Digital Mobile Security System - Dahua Technology ...

DMSS. Digital Mobile Security System. DMSS. features; specifications; accessories; download; DMSS for ios/Android > 1. Multi-Language: English, Spanish ...
Read more

DMSS video 1 - YouTube

Dave Sullivan talking about his tundra tires & JR 28X DMSS System at Joe Nall 2015 - Duration: 5:53. by Kevin Kessler 153 views
Read more

DMSS - Download.com - Free software downloads and software ...

Find DMSS software downloads at CNET Download.com, the most comprehensive source for safe, trusted, and spyware-free downloads on the Web
Read more

DMSS – Windows Apps on Microsoft Store

Windows Phone Surveillance Software DMSS, support single channel realyplay. Support H.264 CIF & D1 resolution. More
Read more

Welcome - DMSS

Welcome to Danish Maritime Supply Service (DMSS) DMSS are providing every service within the logistical part of maritime security and can be contacted 24/7.
Read more

Japan Remote Control CO.,Ltd | Whats DMSS

DMSS is the one of the most reliable 2.4GHz systems available, and is the ultimate in Frequency Hopping Spread Spectrum systems.
Read more

DMSS - Laden Sie Software von DMSS bei iTunes

Hören Sie sich Top-Songs und Alben von DMSS im iTunes Store an und laden Sie die Titel. Songs von DMSS gibt es schon ab .
Read more

Modelflight News: What is JR DMSS? - blogspot.com

How can I get JR DMSS? DMSS is being built into the next generation of JR radio control sets. DMSS sets can be differentiated from earlier JR 2 ...
Read more

Download DMSS-PRO for iphone,DMSS-PRO app free download ...

DMSS-PRO. FREE Current version: 1.56.2 Requirements: Compatible with iPhone, iPod touch, and iPad. Requires iOS 3.0 or later
Read more

Configurar Camaras en telefono DMSS LITE - YouTube

Configurar Camaras en telefono DMSS LITE Electronica Soporte. ... Dahua, Nextvision DMSS para tu smartphone o tablet - Duration: 16:17.
Read more