1988 04 Spring 1988 and Efficiency Study SOUTHERN METHODIST UNI AofRouting the SMU Inter Campus Mail System Pierret Mitchell A ROUTING AND EFFICIENCY STUDY OF THE SMU INTER CAMPUS MAIL SYSTEM PIERRE T MITCHELL OREM 4390 MAY 9 1988 DEPARTMENT OF OPERATIONS RESEARCH AND ENGINEERING MANAGEMENT SCHOOL OF ENGINEERING AND APPLIED SCIENCE DALLAS TEXAS 75275 N31 I I I I I I I I I I I I I I I I I I I I A ROUTING AND EFFICIENCY STUDY OF THE SMU INTER CAMPUS MAIL SYSTEM PIERRE T MITCHELL 0REM4390 MAY 9 198 CONTENTS PAGE INTRODUCTION I PART 1 OPTIMAL ROUTING OF MAIL TRUCKS PROBLEM DESCRIPTION ANALYSiS METHODOLOGY 2 3 PART 11 EFFICIENCY STUDY OF SMU POST OFFICE PROBLEM DESCRIPTION ANALYSIS METHODOLOGY 7 8 RECOMMENDATIONS 11 APPENDIXES A CAMPUS DELIVERY COLLECTION SCHEDULE 12 B MASTER NETWORK MAP INITIAL ADJACENT NODE MATRIX 13 C FLOYD WARSHALL METHOD OF MATRIX MULITPLICATION 15 D FORTRAIvI PROGRAM FOR FLOYD WARSHALL METHOD INiTiAL ADJACENT NODE MATRIX VALUES TRANSFORMED MATRIX SHORTEST PATH VALUES 16 17 E LINEAR PROGRAM FOR TRAVELLING SALESMAN PROBLEM 18 F SOLUTIONS OPTIMAL ROUTE SCHEDULES MAPS 9 30 a m ROUTE 10 30 a m ROUTE 1 10 30 a m ROUTE 2 3 00pnt ROUTE 19 2 1 24 2 7 GI PROJECTED ANNUAL SAVINGS 32 32 CAMPUS MAIL WEEKLY FLOW DATA 33 U Ii 11 I I I I I I I I I 1 I I I I I I INTRODUCTION The SMU postal system is an interesting topic for operations research analysis The system moves so many pieces of mail that even a small improvement in procedures would save time and money My study was prompted by apparent inefficencies which delayed delivery of intercampus mail Items My study has two parts The first part involves the optimal routing of intercampus mail delivery trucks which travel around to different stops on campus for delivery pickup of mail The second part of my study focuses on the amount of mail flow for the different stops and ways to make the sorting of this mail more efficient Initially the second part of this s t udy s to be a simulation of the mail system and would have been the main focus of my analysis but many factors impeded my progress I will discuss them in Part II of this study and the routing of the delivery trucks turned out to be a formidable but interesting new area in which to focus my efforts U I I PART I OPTIMAL ROUTING OF MAIL TRUCKS I I I I I I I I I I I 1 PROBLEM DESCRIPTION The current schedule for the delivery of mail both intercampus and U S mail included is given in Appendix A The schedule is well known to all postal employees and the administration at SMU and I had to improve the mail routes without changing the schedule so as not to largely disturb the system and have my recommendations thrown out due to the amount of effort required to change over to a new system The delivery and pickup times were determined in accordance with the needs of SMU administration faculty and postal staff For example the Admissions department requires that they receive their mail by 8 30 a m Therefore given the routes listed in Appendix A I intended to formulate optimal route schedules for the main four routes 9 30 a m 10 30 a m routes I II and 3 00 p m so as to minimize the time and cost that the trucks spend delivering the mail 2 U I I I I I I I I SI I I I I I I I I I ANALYSIS METHODOLOGY The first step in my analysis was to model the SW campus as a network with street intersections and mail delivery stops as nodes The arc associated arc values were the times that it took to travel from one node to its adjacent nodes I used times for the arc values rather than distances because distance values do not give an accurate representation of driving through the campus Varying traffic densities or stop signs stop lights will produce different time values but not different distance values One of my assumptions was that some of the delivery stops close enough to Street intersections did not warrant creating additional nodes For example the Umphrey Lee center has a mail dropoff which is located at the end of a dead end inlet Since only one entrance exit exists creating an an additional node would be ineffective Jor ex ampie I assumed that the intersection of the inlet dead end service road behind the Umphrey Lee center and Hillcrest Ave is the mail dropoff point I gathered my arc time values t i j s by driving around campus and measuring the time it took to get from node i to node j I used my roomates car Ford Mustang and drove it as consistently and slowly as possible so as to emulate the mail trucks speed I took two sets of times on a Sunday and a Monday and averaged them to obtain a general flow pattern which emulates driving around campus I also double checked Mondays values by riding around in the mail truck on Monday and comparing time values with those obtained by driving the Mustang The values were very close and I assumed that my data was sufficiently accurate The ideal way to perform an analysis would be to formulate time networks for every delivery time since traffic densities will vary accordingly For example traffic will be heavier at 9 00 10 00 11 00 for MWF classes and 9 30 11 00 12 30 for TTH classes due to the students arriving leaving from class Also since the mail trucks 3 I I also don t strictly adhere to their schedules e g the 9 30 truck will leave at 10 00 10 30 when the amount of mail is heavy trying to assign traffic flows for a specific route is a highly stochastic procedure and I will assume that my network data is sufficiently accurate I Once my network was established I set up a matrix for the time values for adjacent nodes the master network map and initial matrix are given in Appendix B I then looked at each route set up a network of t i j s for the every combination of selected nodes and found the optimal route i e the travelling salesman problem The problem in finding these time values however is that they are not directly available All I have is time values for adjacent nodes and I need time values for all t i j s One solution would involve setting up multiple shortest path networks and solving them yet such acho ptogramming is highly inefficient Luckily a method exists for transforming the initial adjacent node matrix to a matrix which contains the shortest path for every pair of nodes I I I I The method I m using is a streamlined version of an algorithm developed by Floyd and Warshall The Floyd Warshall method involves performing k matrix self mulitplications …