Learning Outcomes
In this project you will demonstrate your understanding of structures and arrays of structures, and will develop a computational solution for a non-trivial problem. You are also expected to make extensive use of functions; and to demonstrate that you have adopted a clear and elegant programming style. You will find it difficult to create a working solution unless you plan your program carefully in advance, and develop it incrementally.
Path Planning
Path planning is required in many situations, including satnav software and autonomous robot control. As one specific example, the item “pickers” employed in Amazon’s warehouses (soon to be opened in Australia) follow instructions that specify their routing through the warehouse as they assemble each order, with the route determined in advance so as to minimize walking time (or riding time, the warehouses are big). The pickers might also be robotic devices, controlled by wireless network from a central routeplanner. Your task in this project is to develop a program that compares and evaluates such routings, based on a pool of incoming orders that must be picked, packaged, and despatched.
In particular, we will assume that the bins form a two-dimensional grid, and are laid out in a regular pattern of straight-line corridors to allow easy navigation. Each bin is labeled with coordinates; to keep it simple in this project, we will assume that each location is specified by a numeric bin number to indicate a row, and an alphabetic column number. For example, bin 3a is the third one in the first column (corridor). The bins on both sides of each corridor have the same address, and rows are counted from one (Amazon doesn’t like the number zero) and columns from the letter “a”.
Figure 1: Example warehouse layout in which there are eight rows of bins and eight corridors to access them. Pickers enter the warehouse at the marked entry location; then must follow the directions permitted by the arrows; and finally leave the warehouse via the marked exit location.
Figure 1 illustrates such an arrangement, with (in the example) eight rows of bins, and eight corridors to access them. Warehouses will always have the general rectangular “shape” that is depicted, including a single entry point and a single exit point in the top row; but might have different numbers of corridors, and different numbers of bins per row. In general you may assume that there will be at most 99 bins per corridor, and at most 26 corridors (that is, the maximum corridor label is “z”). You may also assume that the number of corridors will be even, so that the exit is opposite an “up” corridor, as shown. Finally, to avoid collisions between trolleys (remember, this might be automated, and the pickers might be robots), each pathway is one-way.
Note that a very large number of simplifying assumptions are being made in this layout: that there is no third dimension (height) associated with the bin addresses (clearly unlikely to be true); that pickers can always move without being blocked by other pickers accessing the same corridor (clearly unlikely to be true); and that there are no “shortcut” links between the long straight corridors (like there are at IKEA if you know where to look for them); and so on. Nor will we pay any attention to how items get in to the bins. That part of it is someone else’s problem, working the night shift.
Stage 1 - Designing Structures, Reading and Printing (marks up to 6/20)
Orders to the warehouse are generated via a web e-store interface that captures a customer id and a list of items that make up that order; then another program (still not the one we are writing here) determines the location of the item(s) being purchased in terms of row number and corridor number and rewrites the order to a file in text format. That file is then the input to the program you must write. For example, the following describes an order for five items requested by a customer:
2010161 5
123 1a 876 2a 654 5d 751 3b 431 2b
In this example, customer 2010161 has ordered 5 items, with item 123 located in bin number 1a, and so on. Each input file contains multiple such customer orders.
Write a set of typedef and struct declarations to model the situation described; and write suitable functions to read an input file into these internal structures. For input file data1.txt, which covers a total of six customer’s orders and 26 items purchased, and includes as its first order the five-item purchase shown above, the required output (showing the first and last customer orders in full) is:
Stage 1
------
orders: 6
items : 26
customer 2010161, 5 items, bins: 1a 2a 5d 3b 2b
customer 1856512, 7 items, bins: 4f 3g 2f 8g 6h 2h 1g
You are expected to use struct types for all data storage, including ones that contain arrays as components. To keep your program space requirements compact, you should assume that each input file contains orders from at most 100 customers, and that each customer purchases at most 10 items in any order. In a real e-store these limits would be much higher, of course.
Stage 2 - Sorting Into “Pick” Order (marks up to 12/20)
Given the corridor arrangements shown in Figure 1, pickers cannot backtrack - they can only visit each corridor once, and must pick the required items in the correct sequence. In particular, in the odd-lettered corridors “a” and “c” and so on, the bins must be visited in increasing numeric order, whereas in corridors “b” and “d” and so on, the bins must be visited in decreasing numeric order.
Add functionality to your program so that each of the customer orders is sorted into pick order. For example, the required additional output from this stage for file data1.txt also shows the first and last customer orders, after they have been sorted:
Stage 2
------
customer 2010161, 5 items, bins: 1a 2a 3b 2b 5d
customer 1856512, 7 items, bins: 4f 2f 1g 3g 8g 6h 2h
Stage 3 - Calculating Pick Times (marks up to 16/20)
The efficiency of the warehouse is determined by the average time required to pick one order. Time, in turn, is proportional to the total travel distance involved. If we suppose that distance between corridor centers is 6.4 metres, then in the arrangement shown in Figure 1 the total horizontal distance traveled from entry point to exit point is always 7 * 6.4 = 44.8 metres, because backtracking is not possible.
To this must be added the vertical (both down and up) distances traveled. Suppose that the distance between bin centers is 3.8 metres, and that the paths at top and bottom of the warehouse are the same width as a single bin. Then, to pick an item from bin 1a requires a total vertical travel distance of (1 + 2 * 9) * 3.8 = 72.2 metres, because the whole of corridor “a” must be traversed “downward”, and then a whole “upward” corridor must also be traveled; because the top pathway is also one bin wide (and half of that top pathway is covered on entry, and half on exit); and because traveling a whole corridor is equivalent to moving past 9 bins. The four-item order 1a 2a 3b 1b has the same total distance of 44.8 + 72.2 = 117.0 metres.
In this stage, modify your program so that:
- values for the number of rows and the number of corridors are accessed from the command-line (you will find the function atof() useful for this), in that order; and then use those two values to
- compute and print the distance traveled for the first customer order and last customer order, and the average travel distance over all of the customer orders in the input file.
Note that the least-cost pick path should always be taken - for each order, the minimum required number of corridors should be entered to satisfy that order. For data1.txt the output for this stage (with a bigger warehouse than is depicted in Figure 1) should be:
mac: ./myass2 10 12 lt; data1.txt
[Stage 1 and 2 output, see the FAQ page for a full example]
Stage 3
------
warehouse has 10 rows and 12 columns
customer 2010161, 5 items, pick distance: 241.4 metres
customer 1856512, 7 items, pick distance: 241.4 metres
average distance per order over 6 orders: 227.5 metres
Stage 4 - Reducing the Cost (marks up to 20/20)
Having a picker working on only one order at a time is clearly inefficient, and the Amazon management is interested in modeling the possible cost savings that would arise if pickers were able to simultaneously pick for two orders, provided that they are never required to carry more than 10 items at any given time. For example, in data1.txt, the first two orders could be given to one picker, and the 3rd and 4th orders also assigned to a second picker. The last two orders in that input file are too big to be combined with each other, and so require a picker each. That is, one simple strategy to reduce costs is to check consecutive pairs of orders, and if their total item count is less than or equal to 10, hand both to the same picker:
Stage 4
------
pickers required: 4
average distance per order over 6 orders: 174.9 metres
A Note on Algorithms
The minimum required approach to Stage 4 is to consider consecutive pairs of orders, as sketched above. But you are free to adopt any “improved” approach in Stage 4 that you wish, and there are other possibilities you might like to explore if you find you have spare time on your hands. For example, you might choose to try and find pairs of orders in the input data that have exactly 10 items between them; or might like to try and find pairs of orders that have the same or similar corridors used. That is, there is no single “right” answer to the Stage 4 problem. So be sure to provide extensive comments in your programs to help the markers understand the particular mechanism you have decided to implement.
The boring stuff…
This project is worth 20% of your final mark. A rubric explaining the marking expectations will be provided on the FAQ page.
You need to submit your program for assessment; detailed instructions on how to do that will be posted on the LMS once submissions are opened. Submission will not be done via the LMS; instead you will need to log in to a Unix server and submit your files to a software system known as submit. You can (and should) use submit both early and often - to get used to the way it works, and also to check that your program compiles correctly on our test system, which has some different characteristics to the lab machines. Failure to follow this simple advice is highly likely to result in tears. Only the last submission that you make before the deadline will be marked.